Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCollinearities in Kinetic Point Sets
128
0
0.0
(
0
)
Added by
Justin Wesley Smith
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $operatorname{rb-index}(k)$ be the maximum of $operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $operatorname{rb-index}(k) eq k$, and we prove that for $kge 5$, [ frac{40lfloor (k-1)/2 rfloor -8}{19} %Birgit: leqoperatorname{rb-index}(k)leq 10 bigglfloorfrac{k}{7}biggrfloor + 11. ] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 lfloorfrac{k}{7}rfloor + 11$ vertices can be computed in $O(nlog n)$ time.
We give an overview of the 2020 Computational Geometry Challenge, which targeted the problem of partitioning the convex hull of a given planar point set P into the smallest number of convex faces, such that no point of P is contained in the interior of a face.
We consider straight line drawings of a planar graph $G$ with possible edge crossings. The emph{untangling problem} is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let $fix(G)$ denote the maximum number of vertices that can be left fixed in the worst case. In the emph{allocation problem}, we are given a planar graph $G$ on $n$ vertices together with an $n$-point set $X$ in the plane and have to draw $G$ without edge crossings so that as many vertices as possible are located in $X$. Let $fit(G)$ denote the maximum number of points fitting this purpose in the worst case. As $fix(G)le fit(G)$, we are interested in upper bounds for the latter and lower bounds for the former parameter. For each $epsilon>0$, we construct an infinite sequence of graphs with $fit(G)=O(n^{sigma+epsilon})$, where $sigma<0.99$ is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with $fit(G)=o(n)$. On the other hand, we prove that $fix(G)gesqrt{n/30}$ for all $G$ with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs. Our upper bound for $fit(G)$ is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for $fix(G)$, we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.
We study the geodesic Voronoi diagram of a set $S$ of $n$ linearly moving sites inside a static simple polygon $P$ with $m$ vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector KDS handles each event in $O(log m)$ time, and our Voronoi center handles each event in $O(log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
