Computational Geometry (cs.CG)

  • PDF
    Many algorithms, especially in the field of computational geometry, are based on the premise that arithmetic operations are performed exactly. Real machines are based on inexact floating-point arithmetic. Various number types have been developed to close this gap by providing exact computation or ensuring exact decisions. In this report we describe the implementation of an extension to the exact-decisions number type Real_algebraic that enables us to take advantage of multiple processing units.
  • PDF
    We prove that the following problem is complete for the existential theory of the reals: Given a planar graph and a polygonal region, with some vertices of the graph assigned to points on the boundary of the region, place the remaining vertices to create a planar straight-line drawing of the graph inside the region. This strengthens an NP-hardness result by Patrignani on extending partial planar graph drawings. Our result is one of the first showing that a problem of drawing planar graphs with straight-line edges is hard for the existential theory of the reals. The complexity of the problem is open in the case of a simply connected region. We also show that, even for integer input coordinates, it is possible that drawing a graph in a polygonal region requires some vertices to be placed at irrational coordinates. By contrast, the coordinates are known to be bounded in the special case of a convex region, or for drawing a path in any polygonal region.
  • PDF
    We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of a 3-connected graph, we show how to morph the drawing to one with convex faces while maintaining planarity at all times. Furthermore, the morph is convexity increasing, meaning that angles of inner faces never change from convex to reflex. We give a polynomial time algorithm that constructs such a morph as a composition of a linear number of steps where each step either moves vertices along horizontal lines or moves vertices along vertical lines.
  • PDF
    We consider practical methods for the problem of finding a minimum-weight triangulation (MWT) of a planar point set, a classic problem of computational geometry with many applications. While Mulzer and Rote proved in 2006 that computing an MWT is NP-hard, Beirouti and Snoeyink showed in 1998 that computing provably optimal solutions for MWT instances of up to 80,000 uniformly distributed points is possible, making use of clever heuristics that are based on geometric insights. We show that these techniques can be refined and extended to instances of much bigger size and different type, based on an array of modifications and parallelizations in combination with more efficient geometric encodings and data structures. As a result, we are able to solve MWT instances with up to 30,000,000 uniformly distributed points in less than 4 minutes to provable optimality. Moreover, we can compute optimal solutions for a vast array of other benchmark instances that are not uniformly distributed, including normally distributed instances (up to 30,000,000 points), all point sets in the TSPLIB (up to 85,900 points), and VLSI instances with up to 744,710 points. This demonstrates that from a practical point of view, MWT instances can be handled quite well, despite their theoretical difficulty.
  • PDF
    Let $R$ and $B$ be sets of $n$ red and $n$ blue points in the plane, respectively, with $P = R \cup B$. Let $M$ be a perfect matching between points from $R$ and $B$, using $n$ straight line segments to match the points, that is, each point is an endpoint of exactly one line segment, and each line segment has one red and one blue endpoint. We forbid line segments to cross. Denote the length of a longest line segment in $M$ with $bn(M)$, which we also call the \intro[~]value, bn of $M$. We aim to find a matching under given constraints that minimizes $bn(M)$. Any such matching is called a \intro[~]bottleneck matching of $P$.
  • PDF
    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(n\log\log n+m\log 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.
  • PDF
    We develop an randomized approximation algorithm for the size of set union problem $\arrowvert A_1\cup A_2\cup...\cup A_m\arrowvert$, which given a list of sets $A_1,...,A_m$ with approximate set size $m_i$ for $A_i$ with $m_i\in \left((1-\beta_L)|A_i|, (1+\beta_R)|A_i|\right)$, and biased random generators with $Prob(x=\randomElm(A_i))\in \left[{1-\alpha_L\over |A_i|},{1+\alpha_R\over |A_i|}\right]$ for each input set $A_i$ and element $x\in A_i,$ where $i=1, 2, ..., m$. The approximation ratio for $\arrowvert A_1\cup A_2\cup...\cup A_m\arrowvert$ is in the range $[(1-\epsilon)(1-\alpha_L)(1-\beta_L), (1+\epsilon)(1+\alpha_R)(1+\beta_R)]$ for any $\epsilon\in (0,1)$, where $\alpha_L, \alpha_R, \beta_L,\beta_R\in (0,1)$. The complexity of the algorithm is measured by both time complexity, and round complexity. The algorithm is allowed to make multiple membership queries and get random elements from the input sets in one round. Our algorithm makes adaptive accesses to input sets with multiple rounds. Our algorithm gives an approximation scheme with $O(\setCount\cdot(\log \setCount)^{O(1)})$ running time and $O(\log m)$ rounds, where $m$ is the number of sets. Our algorithm can handle input sets that can generate random elements with bias, and its approximation ratio depends on the bias. Our algorithm gives a flexible tradeoff with time complexity $O\left(\setCount^{1+\xi}\right)$ and round complexity $O\left({1\over \xi}\right)$ for any $\xi\in(0,1)$.