Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTopological Stability of Kinetic $k$-Centers
194
0
0.0
(
0
)
Added by
Jules Wulms
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the $k$-center problem in a kinetic setting: given a set of continuously moving points $P$ in the plane, determine a set of $k$ (moving) disks that cover $P$ at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model allows positive results only for $k<3$. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of $k$-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution -- the topological stability ratio -- considering various metrics and various optimization criteria. For $k = 2$ we provide tight bounds, and for small $k > 2$ we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant $k$.
rate research
Read More
We study three orientation-based shape descriptors on a set of continuously moving points: the first principal component, the smallest oriented bounding box and the thinnest strip. Each of these shape descriptors essentially defines a cost capturing the quality of the descriptor and uses the orientation that minimizes the cost. This optimal orientation may be very unstable as the points are moving, which is undesirable in many practical scenarios. If we bound the speed with which the orientation of the descriptor may change, this may lower the quality of the resulting shape descriptor. In this paper we study the trade-off between stability and quality of these shape descriptors. We first show that there is no stateless algorithm, an algorithm that keeps no state over time, that both approximates the minimum cost of a shape descriptor and achieves continuous motion for the shape descriptor. On the other hand, if we can use the previous state of the shape descriptor to compute the new state, we can define chasing algorithms that attempt to follow the optimal orientation with bounded speed. We show that, under mild conditions, chasing algorithms with sufficient bounded speed approximate the optimal cost at all times for oriented bounding boxes and strips. The analysis of such chasing algorithms is challenging and has received little attention in literature, hence we believe that our methods used in this analysis are of independent interest.
We consider the $k$-center problem in which the centers are constrained to lie on two lines. Given a set of $n$ weighted points in the plane, we want to locate up to $k$ centers on two parallel lines. We present an $O(nlog^2 n)$ time algorithm, which minimizes the weighted distance from any point to a center. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithms run in $O(nlog^2 n)$ time also in this case.
We give an algebraic proof of the equivalence of equivariant K-semistability (resp. equivariant K-polystability) with geometric K-semistability (resp. geometric K-polystability). Along the way we also prove the existence and uniqueness of minimal optimal destabilizing centers on K-unstable log Fano pairs.
We address the problem of curvature estimation from sampled compact sets. The main contribution is a stability result: we show that the gaussian, mean or anisotropic curvature measures of the offset of a compact set K with positive $mu$-reach can be estimated by the same curvature measures of the offset of a compact set K close to K in the Hausdorff sense. We show how these curvature measures can be computed for finite unions of balls. The curvature measures of the offset of a compact set with positive $mu$-reach can thus be approximated by the curvature measures of the offset of a point-cloud sample. These results can also be interpreted as a framework for an effective and robust notion of curvature.
Let $P$ be a set of $n$ points in the plane, each point moving along a given trajectory. A {em $k$-collinearity} is a pair $(L,t)$ of a line $L$ and a time $t$ such that $L$ contains at least $k$ points at time $t$, the points along $L$ do not all coincide, and not all of them are collinear at all times. We show that, if the points move with constant velocity, then the number of 3-collinearities is at most $2binom{n}{3}$, and this bound is tight. There are $n$ points having $Omega(n^3/k^4 + n^2/k^2)$ distinct $k$-collinearities. Thus, the number of $k$-collinearities among $n$ points, for constant $k$, is $O(n^3)$, and this bound is asymptotically tight. In addition, there are $n$ points, moving in pairwise distinct directions with different speeds, such that no three points are ever collinear.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
