Science

Our work on the Computational Geometry Challenge 2019 on area-optimal polygonizations is based on two key components: (1) sampling the search space to obtain initial polygonizations and (2) optimizing such a polygonizations. Among other heuristics for obtaining polygonizations for a given set P of input points, we discuss how to combine 2-opt moves with a line sweep to convert an initial random (non-simple) polygon whose vertices are given by P into a polygonization P. The actual optimization relies on a constrained triangulation of the interior and exterior of a polygonization to speed-up local modifications of the polygonization to increase or decrease its area.

a weighted bisector graph is a geometric graph whose faces are bounded by edges that are portions of multiplicatively weighted bisectors of pairs of (point) sites such that each of its faces is defined by exactly one site. a prominent example of a bisector graph is the multiplicatively weighted voronoi diagram of a finite set of points which induces a tessellation of the plane into voronoi faces bounded by circular arcs and straight-line segments. several algorithms for computing various types of bisector graphs are known. in this paper we reverse the problem: given a partition g of the plane into faces, find a set of points and suitable weights such that g is a bisector graph of the weighted points, if a solution exists. if g is a graph that is regular of degree three then we can decide in o(m) time whether it is a bisector graph, where m denotes the combinatorial complexity of g. in the same time we can identify up to two candidate solutions such that g could be their multiplicatively weighted voronoi diagram. additionally, we show that it is possible to recognize g as a multiplicatively weighted voronoi diagram and find all possible solutions in o(mlog⁡m) time if g is given by a set of disconnected lines and circles

We present Cgal implementations of two algorithms for computing straight skeletons in the plane, based on exact arithmetic. One code, named Surfer2, can handle multiplicatively weighted planar straight-line graphs (PSLGs) while our second code, Monos, is specifically targeted at monotone polygons. Both codes are available on GitHub. We discuss algorithmic as well as implementational and engineering details of both codes. Furthermore, we present the results of an extensive performance evaluation in which we compared Surfer2 and Monos to the straight-skeleton package included in Cgal. It is not surprising that our special-purpose code Monos outperforms Cgal's straight-skeleton implementation. But our tests provide ample evidence that also Surfer2 can be expected to be faster and to consume significantly less memory than the Cgal code. And, of course, Surfer2 is more versatile because it can handle multiplicative weights and general PSLGs as input. Thus, Surfer2 currently is the fastest and most general straight-skeleton code available.

The Salzburg Database is a repository of polygonal areas of various classes and sizes, with and without holes. Positive weights are assigned to all edges of all polygons. We introduce this collection and describe the generators that produced its polygons. The source codes for all generators as well as the polygons generated are publicly available.

Our work on minimum convex decompositions is based on two key components: (1) different strategies for computing initial decompositions, partly adapted to the characteristics of the input data, and (2) local optimizations for reducing the number of convex faces of a decomposition. We discuss our main heuristics and show how they helped to reduce the face count.

We present C++ implementations of two algorithms for computing straight skeletons in the plane, based on exact arithmetic. One code, named \textscSurfer2, can handle multiplicatively weighted planar straight-line graphs (PSLGs) while our second code, \textscMonos, is specifically targeted at monotone polygons. Both codes are available on GitHub. We sketch implementational and engineering details and discuss the results of an extensive performance evaluation in which we compared \textscSurfer2 and \textscMonos to the straight-skeleton package included in CGAL. Our tests provide ample evidence that both implementations can be expected to be faster and to consume significantly less memory than the CGAL code.

The Salzburg Database is a repository of polygonal areas of various classes and sizes, with and without holes. Positive weights are assigned to all edges of all polygons. We introduce this collection and briefly describe the generators that produced its polygons. The source codes for all generators as well as the polygons generated are publicly available.

We present C++ implementations of two algorithms for computing straight skeletons in the plane, based on exact arithmetic. One code, named \textscSurfer2, can handle multiplicatively weighted planar straight-line graphs (PSLGs) while our second code, \textscMonos, is specifically targeted at monotone polygons. Both codes are available on GitHub. We discuss algorithmic as well as implementational and engineering details of both codes. Furthermore, we present the results of an extensive performance evaluation in which we compared \textscSurfer2 and \textscMonos to the straight-skeleton package included in CGAL. It is not surprising that our special-purpose code \textscMonos outperforms CGAL's straight-skeleton implementation. But our tests provide ample evidence that also \textscSurfer2 can be expected to be faster and to consume significantly less memory than the CGAL code. And, of course, \textscSurfer2 is more versatile because it can handle multiplicative weights and general PSLGs as input. Thus, \textscSurfer2 currently is the fastest and most general straight-skeleton code available.

We present two software packages for computating straight skeletons: \textscMonos, our implementation of an algorithm by Biedl et al.~(2015), computes the straight skeleton of a monotone input polygon, and \textscSurfer2 implements a generalization of an algorithm by Aichholzer and Aurenhammer~(1998) to handle multiplicatively-weighted planar straight-line graphs as input. The graphical user interfaces that ship with our codes support step-by-step computations, where each event can be investigated and studied by the user. This makes them a canonical candidate for educational purposes and detailed event analyses. Both codes are freely available on GitHub.

We extend results by Biedl et al. (ISVD’13) on the recognition and reconstruction of straight skeletons: Given a geometric tree G, can we recognize whether G resembles a weighted straight skeleton S and, if so, can we reconstruct an appropriate polygonal input P and an appropriate positive weight function σ such that S(P, σ) = G? We show that a solution polygon P and a weight function σ can be found in O(n) time and space for a geometric tree G with n faces if at most one node of G has two incident edges that span an angle greater than π. In addition, we show that G implicitly encodes enough information such that all other weighted bisectors of any solution P can be obtained from G without explicitly computing P.

We consider multiplicatively weighted points, axis-aligned rectangular boxes and axis- aligned straight-line segments in the plane as input sites and study Voronoi diagrams of these sites in the maximum norm. For n weighted input sites we establish a tight Θ(n²) worst-case bound on the combinatorial complexity of their Voronoi diagram and introduce an incremental algorithm that allows its computation in O(n² log n) time. Our approach also yields a truly simple O(n log n) algorithm for solving the one-dimensional version of this problem, where all weighted sites lie on a line.

We introduce a simple algorithm to construct the straight skeleton of an n-vertex orthogonal monotone polygon in optimal O(n) time and space.

We extend the work by Huber and Held (IJCGA 2012) on straight-skeleton computation based on motorcycle graphs to positively weighted skeletons. Resorting to a line arrangement induced by the r reflex vertices of a simple n-vertex polygon P allows to compute the weighted straight skeleton of P in O(n² + r³/k + nr log n) time and O(n + kr) space, for an arbitrary positive integer k with 1 ≤ k ≤ r.

Piecewise-linear terrains (“roofs”) over simple polygons were first studied by Aichholzer et al. (J. UCS 1995) in their work on straight skeletons of polygons. We show how to construct a roof over the polygonal footprint of a building that has minimum or maximum volume among all roofs that drain water. Our algorithm for computing such a roof extends the standard plane-sweep approach known from the theory of straight skeletons by additional events. For both types of roofs our algorithm runs in 𝒪(n³ log n) time for a simple polygon with n vertices.

We present an experimental study of strategies for triangulating polygons in parallel on multi-core machines, including the parallel computation of constrained Delaunay triangulations. As usual, we call three consecutive vertices of a (planar) polygon an ear if the triangle that is spanned by them is completely inside the polygon. Extensive tests on thousands of sample polygons indicate that about 50% of vertices of most polygons form ears. This experimental result suggests that polygon-triangulation algorithms based on ear clipping might be well-suited for parallelization. We discuss three different approaches to parallelizing ear clipping, and we present a parallel edge-flipping algorithm for converting a triangulation into a constrained Delaunay triangulation. All algorithms were implemented as part of Held's FIST framework. We report on our experimental findings, which show that the most promising method achieves an average speedup of 2–3 on a quad-core processor. In any case, our new triangulation code is faster than the sequential triangulation codes Triangle (by Shewchuk) and FIST.

We study Voronoi diagrams of n weighted points in the plane in the maximum norm. We establish a tight Θ(n²) worst-case combinatorial bound for such a Voronoi diagram and introduce an incremental construction algorithm that allows its computation in O(n² log n) time.

We extend the work by Huber and Held (IJCGA 2012) on straight-skeleton computation based on motorcycle graphs to positively weighted skeletons. Resorting to a line arrangement induced by the r reflex vertices of a simple n-vertex polygon P allows to compute the weighted straight skeleton of P in O(n² + r³/k + nr log n) time and O(n + kr) space, for an arbitrary positive integer k with 1 ≤ k ≤ r.

Piecewise-linear terrains (``roofs'') over simple polygons were studied by Aichholzer et al. (1995) in their work on straight skeletons of polygons. We show how to construct a roof over a simple polygon that has minimum (or maximum) volume among all roofs that drain water. Such a maximum-volume (minimum-volume) roof can have quadratic (maybe cubic, resp.) number of facets. Our algorithm for computing such a roof extends the standard wavefront propagation known from the theory of straight skeletons by two additional events. Both the minimum-volume and the maximum-volume roof of a simple polygon with n vertices can be computed in \mathcalO(n³ \log n) time.

We present an experimental study of different strategies for triangulating polygons in parallel. As usual, we call three consecutive vertices of a polygon an ear if the triangle that is spanned by them is completely inside of the polygon. Extensive tests on thousands of sample polygons indicate that most polygons have a linear number of ears. This experimental result suggests that polygon-triangulation algorithms based on ear clipping might be well-suited for parallelization. We discuss three different on-core approaches to parallelizing ear clipping and report on our experimental findings. Extensive tests show that the most promising method achieves a speedup by a factor of roughly k on a machine with k cores.

We present an experimental study of different strate- gies for triangulating polygons in parallel. As usual, we call three consecutive vertices of a polygon an ear if the triangle that is spanned by them is completely in- side the polygon. Extensive tests on thousands of sam- ple polygons indicate that about 50% of the vertices of most polygons form ears, which suggests that polygon- triangulation algorithms based on ear-clipping might be well-suited for parallelization. We discuss three differ- ent on-core approaches to parallelizing ear clipping and report on our experimental findings. Extensive tests show that the most promising method achieves an av- erage speedup of about 3 on a quad-core processor.

In this work we review five different triangulation algorithms and present two of our own. First, two well known algorithms are surveyed: ear-clipping and monotone subdivision. Then, three constrained Delaunay triangulation algorithms are discussed in detail: the first uses a Fortune-like sweep-line approach, the second uses a randomized incremental construction method, and the third is constructing the triangulation in parallel on the GPU. We also present our two parallel ear-clipping methods. One is a divide and conquer approach where the simple input polygon is divided in linear time. The other is a mark and cut extension which uses a sequential mark phase and a parallel cut phase. Both are tested extensively and the results are discussed.