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.

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 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 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.

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.

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^3 log n) time for a simple polygon with n vertices.