In the conflict-free coloring problem, for a given range space, we want to bound the minimum value F(n) such that every set P of n points can be colored with F(n) colors with the property that every nonempty range contains a unique color. We prove a new upper bound O(n^{0.368}) with respect to orthogonal ranges in two dimensions (i.e., axis-parallel rectangles), which is the first improvement over the previous bound O(n^{0.382}) by Ajwani, Elbassioni, Govindarajan, and Ray [SPAA'07]. This result leads to an O(n^{1-0.632/2^{d-2}}) upper bound with respect to orthogonal ranges (boxes) in dimension d, and also an O(n^{1-0.632/(2^{d-3}-0.368)}) upper bound with respect to dominance ranges (orthants) in dimension d >= 4.
We also observe that combinatorial results on conflict-free coloring can be applied to the analysis of approximation algorithms for discrete versions of geometric independent set problems. Here, given a set P of (weighted) points and a set S of ranges, we want to select the largest(-weight) subset Q of P with the property that every range of S contains at most one point of Q. We obtain, for example, a randomized O(n^{0.368})-approximation algorithm for this problem with respect to orthogonal ranges in the plane.
We consider the problem of finding the shortest curve in the plane that has unit width. This problem was first posed as the "river shore" puzzle by Ogilvy (1972) and is related to the area of on-line searching. Adhikari and Pitman (1989) proved that the optimal solution has length 2.2782... We present a simpler proof, which exploits the fact that the width of a polygon does not decrease under a certain convexification operation.
We prove that there is a polyhedron with genus 6 whose faces are orthogonal polygons (equivalently, rectangles) and yet the angles between some faces are not multiples of 90 degrees, so the polyhedron itself is not orthogonal. On the other hand, we prove that any such polyhedron must have genus at least 3. These results improve the bounds of Donoso and O'Rourke (2001) that there are nonorthogonal polyhedra with orthogonal faces and genus 7 or larger, and any such polyhedron must have genus at least 2. We also demonstrate nonoverlapping one-piece edge-unfoldings (nets) for the genus-7 and genus-6 polyhedra.
This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q with k and n vertices, respectively (k < n), the number of edges and vertices bounding a single face of the complement of the Minkowski sum P + Q is Theta(nk alpha(k)) in the worst case. The lower bound comes from a construction based on lower envelopes of line segments; the upper bound comes from a combinatorial bound on Davenport-Schinzel sequences that satisfy two alternation conditions.
The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.