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.

- PDF file
- PDF talk slides
- In
*Proc. 28th ACM Symposium on Computational Geometry (SoCG)*, pages 293-302, 2012

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.

- PostScript file | PDF file
- In Proc. 15th Canadian Conference on Computational Geometry (CCCG), pages 73-75, 2003
- The curve is featured in a part of the video
"The asteroid surveying problem and other puzzles":
- In Web Proc. 12th Video Review of Computational Geometry, 2003
- Short description of the video: gzipped PostScript file | PDF file
- Also in Proc. 19th ACM Symposium on Computational Geometry (SoCG), pages 372-373, 2003

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.

- Gzipped postscript file
- In Proc. 14th Canadian Conference on Computational Geometry (CCCG), pages 105-108, 2002

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.

- Postscript file
- In Proc. 7th Canadian Conference on Computational Geometry (CCCG), pages 91-96, 1995

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.

Timothy Chan (Last updated Aug 2023)