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.

We present an O(n log n)-time algorithm that determines whether a given planar n-gon is weakly simple. This improves upon an O(n^2 log n)-time algorithm by [Chang, Erickson, and Xu, SODA, 2015]. Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.

Motivated by applications to graph morphing, we consider the following compatible connectivity-augmentation problem: We are given a labelled n-vertex planar graph, G, that has r ≥ 2 connected components, and k ≥ 2 isomorphic planar straight-line drawings, G1, …, G2, of G. We wish to augment G by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to G1, …, G2 as points and straight-line segments, respectively, to obtain k planar straight-line drawings isomorphic to the augmentation of G. We show that adding Θ(nr1–1/k) edges and vertices to G is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all r ∊ {2, …, n} and k ≥ 2 and is achievable by an algorithm whose running time is O(nr1–1/k) for k = O(1) and whose running time is O(kn2) for general values of k. The lower bound holds for all r ∊ {2, …, n/4} and k ≥ 2.

The order type of a point set in ℝd maps each (d+1)-tuple of points to its orientation (e.g., clockwise or counterclockwise in ℝ2). Two point sets X and Y have the same order type if there exists a mapping f from X to Y for which every (d+1)-tuple (a1, a2, …, ad+1) of X and the corresponding tuple (f(a1), f(a2), …, f(ad+1)) in Y have the same orientation. In this paper we investigate the complexity of determining whether two point sets have the same order type. We provide an O(nd) algorithm for this task, thereby improving upon the O(n⌊3d/2⌋) algorithm of Goodman and Pollack (1983). The algorithm uses only order type queries and also works for abstract order types (or acyclic oriented matroids). Our algorithm is optimal, both in the abstract setting and for realizable points sets if the algorithm only uses order type queries.

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 for every centrally symmetric convex polygon Q, there exists a constant α such that any αk-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Tóth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.