Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLinking disjoint segments into a simple polygon is hard
109
0
0.0
(
0
)
Added by
Minghui Jiang
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Deciding whether a family of disjoint line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard.
rate research
Read More
Deciding whether a family of disjoint axis-parallel line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard.
We construct a family of 17 disjoint axis-parallel line segments in the plane that do not admit a circumscribing polygon.
Given a planar straight-line graph $G=(V,E)$ in $mathbb{R}^2$, a emph{circumscribing polygon} of $G$ is a simple polygon $P$ whose vertex set is $V$, and every edge in $E$ is either an edge or an internal diagonal of $P$. A circumscribing polygon is a emph{polygonization} for $G$ if every edge in $E$ is an edge of $P$. We prove that every arrangement of $n$ disjoint line segments in the plane has a subset of size $Omega(sqrt{n})$ that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to $mathbb{R}^3$. We show that it is NP-complete to decide whether a given graph $G$ admits a circumscribing polygon, even if $G$ is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization.
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.
Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an $O(nloglog n+mlog m)$- time algorithm to compute the geodesic farthest-point Voronoi diagram of $m$ point sites in a simple $n$-gon. This improves the previously best known algorithm by Aronov et al. [Discrete Comput. Geom. 9(3):217-255, 1993]. In the case that all point sites are on the boundary of the simple polygon, we can compute the geodesic farthest-point Voronoi diagram in $O((n + m) log log n)$ time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
