TY - BOOK

T1 - New results on classical problems in computational geometry in the plane

AU - Abrahamsen, Mikkel

PY - 2017

Y1 - 2017

N2 - In this thesis, we revisit three classical problems in computational geometry in the plane.An obstacle that often occurs as a subproblem in more complicated problems is to compute the common tangents of two disjoint, simple polygons. For instance, the common tangents turn up in problems related to visibility, collision avoidance, shortest paths, etc. We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons—whether they are nested, overlapping, or disjoint—and our algorithm thus also decides this relationship.One of the best-known problems in computational geometry is the art gallery problem, which was already studied in the early 70s. Many variations of the problem have been considered, but here we study the classical version where we are given a simple polygon with vertices at rational coordinates and we have to decide whether a given number of guards can be placed in the polygon so that they guard the entire polygon. We give an explicit example of a polygon where three guards are sufficient, but only if they are placed on specific points with irrational coordinates. If the coordinates of the guards are required to be rational, then four guards are needed. We furthermore prove the much more general result that the art gallery problem is complete for the complexity class ∃ℝ, implying that (1) the art gallery problem is equivalent up to polynomial time reductions to the problem of deciding whether a given system of polynomial equations and inequalities with integer coefficients and any number of variables has a solution, and (2) the art gallery problem is not in the complexity class NP unless NP = ∃ℝ. As a corollary of our construction, we prove that for any real algebraic number α there is an instance of the art gallery problem where one of the coordinates of the guards equals α in any guard set of minimum cardinality. That rules out many geometric approaches to the problem.A natural clustering problem for points in the plane, which has been studied since the early 90s, is the minimum perimeter sum problem. Here, we are given n points and we want to find the way to partition the points into some number k of clusters so that the sum of perimeters of the convex hulls of the clusters is minimum. For the special case of k = 2, the fastest previously known algorithm had quadratic running time and we provide an O(n log4 n) time algorithm.

AB - In this thesis, we revisit three classical problems in computational geometry in the plane.An obstacle that often occurs as a subproblem in more complicated problems is to compute the common tangents of two disjoint, simple polygons. For instance, the common tangents turn up in problems related to visibility, collision avoidance, shortest paths, etc. We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons—whether they are nested, overlapping, or disjoint—and our algorithm thus also decides this relationship.One of the best-known problems in computational geometry is the art gallery problem, which was already studied in the early 70s. Many variations of the problem have been considered, but here we study the classical version where we are given a simple polygon with vertices at rational coordinates and we have to decide whether a given number of guards can be placed in the polygon so that they guard the entire polygon. We give an explicit example of a polygon where three guards are sufficient, but only if they are placed on specific points with irrational coordinates. If the coordinates of the guards are required to be rational, then four guards are needed. We furthermore prove the much more general result that the art gallery problem is complete for the complexity class ∃ℝ, implying that (1) the art gallery problem is equivalent up to polynomial time reductions to the problem of deciding whether a given system of polynomial equations and inequalities with integer coefficients and any number of variables has a solution, and (2) the art gallery problem is not in the complexity class NP unless NP = ∃ℝ. As a corollary of our construction, we prove that for any real algebraic number α there is an instance of the art gallery problem where one of the coordinates of the guards equals α in any guard set of minimum cardinality. That rules out many geometric approaches to the problem.A natural clustering problem for points in the plane, which has been studied since the early 90s, is the minimum perimeter sum problem. Here, we are given n points and we want to find the way to partition the points into some number k of clusters so that the sum of perimeters of the convex hulls of the clusters is minimum. For the special case of k = 2, the fastest previously known algorithm had quadratic running time and we provide an O(n log4 n) time algorithm.

UR - https://soeg.kb.dk/permalink/45KBDK_KGL/fbp0ps/alma99122574329405763

M3 - Ph.D. thesis

BT - New results on classical problems in computational geometry in the plane

PB - Department of Computer Science, Faculty of Science, University of Copenhagen

ER -