Search

Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point-object pairs. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their number is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete. [ABSTRACT FROM AUTHOR]

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k−1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k−1) + 1. Lower bounds are also given for all of the above problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy. [ABSTRACT FROM AUTHOR]

In this paper we consider deflations (inverse pocket flips) of n-gons for small n. We show that every pentagon can be deflated after finitely many deflations, and that any infinite deflation sequence of a pentagon results from deflating an induced quadrilateral on four of the vertices. We describe a family of hexagons that deflate infinitely for a specific deflation sequence, yet induce no infinitely deflating quadrilateral. We also review the known understanding of quadrilateral deflation. [ABSTRACT FROM AUTHOR]

We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the ℓp norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p=1, p=2, and p=∞. For p=2, we reduce the problem to standard convolution, while for p=∞ and p=1, we reduce the problem to (min,+) convolution and (median,+) convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X + Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X + Y matrix. All of our algorithms run in o(n2) time, whereas the obvious algorithms for these problems run in Θ(n2) time. [ABSTRACT FROM AUTHOR]