A covering path for a finite set P of points in the plane is a polygonal path such that every point of P lies on a segment of the path. The vertices of the path need not be at points of P. A covering path is plane if its segments do not cross each other. Let π(n) be the minimum number such that every set of n points in the plane admits a plane covering path with at most π(n) segments. We prove that π(n) ≤ ⌈6n/7⌉. This improves the previous best-known upper bound of ⌈21n/22⌉, due to Biniaz (SoCG 2023). Our proof is constructive and yields a simple O(n log n)-time algorithm for computing a plane covering path.

Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon $\mathcal{R}$, called a district map, is a set of interior disjoint connected polygons called districts whose union equals $\mathcal{R}$. We consider the recombination as the reconfiguration move which takes a subdivision and produces another by merging two adjacent districts, and by splitting them into two connected polygons of the same area as the original districts. The complexity of a map is the number of vertices in the boundaries of its districts. Given two maps with $k$ districts, with complexity $O(n)$, and a perfect matching between districts of the same area in the two maps, we show constructively that $(\log n)^{O(\log k)}$ recombination moves are sufficient to reconfigure one into the other. We also show that $Ω(\log n)$ recombination moves are sometimes necessary even when $k=3$, thus providing a tight bound when $k=O(1)$.

Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k-Partition with slack s, denoted (k,s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with |ni−n/k|≤s, each of which induces a connected subgraph (when s=0, the k parts are perfectly balanced, and we call it k-BCP for short). A recombination is an operation that takes a (k,s)-BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s≥0, we wish to determine whether there exists a sequence of recombinations that transform A into B via (k,s)-BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k, (3) there exist negative instances for s≤n/(3k), and (4) we show that determining whether a sequence of recombination that connects two (k,s)-BCP of a graph G exists is PSPACE-complete when k∈O(nε) and s∈O(n1−ε), for any constant 0<ε≤1. This statement holds even for restricted settings such as when G is an edge-maximal planar graph or when k≥3 and G is planar.

Given a planar straight-line graph G=(V,E) in R^2, a 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 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 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.

For a set R of n red points and a set B of n blue points, a BR-matching is a non-crossing geometric perfect matching where each segment has one endpoint in B and one in R. Two BR-matchings are compatible if their union is also non-crossing. We prove that, for any two distinct BR-matchings M and M', there exists a sequence of BR-matchings M = M1, ..., Mk = M' such that Mi-1 is compatible with Mi. This implies the connectivity of the compatible bichromatic matching graph containing one node for each BR-matching and an edge joining each pair of compatible BR-matchings, thereby answering the open problem posed by Aichholzer et al. in their paper "Compatible matchings for bichromatic plane straight-line graphs".

We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom linkage structure, such that closing the pop-up flattens the linkage without collision. This result solves an open problem of Hara and Sugihara from 2009. We also show how to obtain a more efficient construction for the special case of orthogonal polygons, and how to make 3D orthogonal polyhedra, from pop-ups that open to 90°, 180°, 270°, or 360°.

We prove that for every even set of $n$ pairwise disjoint line segments in the plane in general position, there is another set of n segments such that the 2n segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the Disjoint Compatible Matching Conjecture by Aichholzer et al. [ABD08]. The key tool in our proof is a novel subdivision of the free space around n disjoint line segments into at most n+1 convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees.

Data depth is a statistical analysis method that assigns a numeric value to a point based on its centrality relative to a data set. Examples include the half-space depth (also known as Tukey depth), convex-hull peeling depth and L1 depth. Data depth has significant potential as a data analysis tool. The lack of efficient computational tools for depth based analysis of large high-dimensional data sets, however, prevents it from being in widespread use. We provide an experimental evaluation of several existing depth measures on different types of data sets, recognize problems with the existing measures and suggest modifications. Specifically, we show how the L1 depth contours are not indicative of shape and suggest a PCA-based scaling that handles this problem; we demonstrate how most existing depth measures are unable to cope with multimodal data sets and how the newly suggested proximity graph depth addresses this issue; and we explore how depth measures perform when the underlying distribution is not elliptic. Our experimental tool is of independent interest: it is an interactive software tool for the generation of data sets and visualization of the performance of multiple depth measures. The tool uses a hierarchical render-pipeline to allow for diverse data sets and fine control of the visual result. With this tool, new ideas in the field of data depth can be evaluated visually and quickly, allowing researchers to assess and adjust current depth functions.

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight-line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines then there is a spanning tree where every barrier is crossed by O(√m) tree edges (connectors), and this bound is asymptotically optimal (spanning tree with low stabbing number). Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Constructions with 3 crossings per barrier and 2n total cost provide a lower bound.We obtain tight bounds on the minimum cost spanning tree in the most exciting special case where the barriers are interior disjoint line segments that form a convex subdivision and there is a point in every cell. In particular, we show that there is a spanning tree such that every barrier is crossed by at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are tight.

Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (incident to an angle larger than p). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide---to the best of our knowledge---the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces.

We consider the problem of verifying a simple polygon in the plane using “test points”. A test point is a geometric probe that takes as input a point in Euclidean space, and returns “+” if the point is inside the object being probed or “−” if it is outside. A verification procedure takes as input a description of a target object, including its location and orientation, and it produces a set of test points that are used to verify whether a test object matches the description. We give a procedure for verifying an n-sided, non-degenerate, simple target polygon using 5n test points. This testing strategy works even if the test polygon has n + 1 vertices, and we show a lower bound of 3n + 1 test points for this case. We also give algorithms using O(n) test points for simple polygons that may be degenerate and for test polygons that may have up to n + 2 vertices. All of these algorithms work for polygons with holes. We also discuss extensions of our results to higher dimensions.

Let C+ and C− be two collections of topological discs. The collection of discs is ‘topological’ in the sense that their boundaries are Jordan curves and each pair of Jordan curves intersect at most twice. We prove that the region ∪C+ − ∪C− has combinatorial complexity at most 10n − 30 where p = |C+|, q = |C−| and n = p + q ≥ 5. Moreover, this bound is achievable. We also show less precise bounds that are stated as functions of p and q.

Article Free Access Share on Coping with inconsistencies: a new approach to produce quality triangulations of polygonal domains with holes Authors: Elefterios A. Melissaratos View Profile , Diane L. Souvaine View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992 Pages 202–211https://doi.org/10.1145/142675.142719Published:01 July 1992Publication History 21citation316DownloadsMetricsTotal Citations21Total Downloads316Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of finding the contour of the union of a collection of polygons in which all vertices have integer coordinates and the slopes of the sides belong to a finite fixed collection of orientations is studied from two perspectives. The first is that of determining which algorithms for finding the contour of the union for rectilinear polygons and/or rectangles can be generalized to handle polygons with sides of two or more additional directions while still retaining efficiency. The second is that of determining which algorithms for computing the union of arbitrary polygons in general position can be revised to handle degeneracies and possibly to take advantage of the restricted number of orientations to improve robustness, efficiency, or both. Three distinct rectilinear algorithms are detailed, and general preprocessing and postprocessing procedures which allow all three rectilinear algorithms to operate on polygons of additional orientations are presented. Two general algorithms for computing the contour of union based on line segment intersection algorithms and plane sweeping are also presented and analyzed.>

The goal of this paper is to show that the concept of the shortest path inside a polygonal region contributes to the design of efficient algorithms for certain geometric optimization problems involving simple polygons: computing optimum separators, maximum area or perimeter-inscribed triangles, a minimum area circumscribed concave quadrilateral, or a maximum area contained triangle. The structure for the algorithms presented is as follows: (a) decompose the initial problem into a low-degree polynomial number of optimization problems; (b) solve each individual subproblem in constant time using standard methods of calculus, basic methods of numerical analysis, or linear programming. These same optimization techniques can be applied to splinegons (curved polygons). First a decomposition technique for curved polygons is developed; this technique is substituted for triangulation in creating equally efficient curved versions of the algorithms for the shortest-path tree, ray-shooting, and two-point shortest path problems. The maximum area or perimeter inscribed triangle problem, the minimum area circumscribed concave quadrilateral problem and maximum area contained triangle problem have applications to robotics and stock-cutting. The results of this paper appear in E. A. Melissaratos’s Ph.D. thesis [Mesh Generation and Geometric Optimization, Rutgers University, New Brunswick, NJ, 1991].

We have developed techniques which contribute to efficient algorithms for certain geometric optimization problems involving simple polygons: computing minimum separators, maximum inscribed triangles, a minimum circumscribed concave quadrilateral, or a maximum contained triangle.The structure for our algorithms is as follows: a) decompose the initial problem into a low-degree polynomial number of easy optimization problems; b) solve each individual subproblem in constant time using the methods of cealcu-Ins, standard methods of numerical analysis, or linear programming.The decomposition step uses shorteat path trees inside simple polygons (Guibas et. al.~ 1987) and, in the case of inscribed triangles, produces a new class of polygons, the fan-shaped polygon.By extending the shortest-path algorithm to splinegons, we also generate splinegon-versions of the algorithms for some of the optimization problems.The problems we discuss fall into four subgroups: Separators: If two points z and y lie on the boundary of simple polygon P and define a directed line segment zy C_ P that separates P into two sets PL and Pa, then zy is called a separator.M i n i m u m l e n g t h : The areas of PL and PR are defined by constants KL and KR.Find a separator of minimum length.