We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among non-intersecting line segments, that supports queries in O(log n (loglog n)^2) time and updates in O(log n loglog n) time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring loglog n factors. We further show how to reduce the query time to O(log n loglog n) in the RAM model with randomization. Alternatively, the query time can be lowered to O(log n) if the update time is increased to O(log^{1+eps}n) for any constant eps>0, or vice versa.

- PDF file
- Invited to SIAM Journal on Computing (FOCS special issue)
- In Proc. 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 390-409, 2015

Many standard problems in computational geometry have been solved asymptotically optimally as far as comparison-based algorithms are concerned, but there has been little work focusing on improving the constant factors hidden in big-Oh bounds on the number of comparisons needed. In this paper, we consider orthogonal-type problems and present a number of results that achieve optimality in the constant factors of the leading terms, including:

- an algorithm for the 2D maxima problem that uses n lg h + O(n sqrt{lg h}) comparisons, where h denotes the output size;
- a randomized algorithm for the 3D maxima problem that uses n lg h + O(n lg^{2/3} h) expected number of comparisons;
- a randomized algorithm for detecting intersections among a set of orthogonal line segments that uses n lg n + O(n sqrt{lg n}) expected number of comparisons;
- a data structure for point location among 3D disjoint axis-parallel boxes that can answer queries in (3/2)lg n + O(lg lg n) comparisons;
- a data structure for point location in a 3D box subdivision that can answer queries in (4/3)lg n + O(sqrt{lg n}) comparisons.

Our algorithms and data structures use a variety of techniques, including Seidel and Adamy's planar point location method, weighted binary search, and height-optimal BSP trees.

- PDF file
- Discrete and Computational Geometry, 53:489-513, 2015 (SoCG special issue)
- In Proc. 30th Symposium on Computational Geometry (SoCG), pages 40-49, 2014

We answer a basic data structuring question (for example, raised by Dietz and Raman back in SODA 1991): can van Emde Boas trees be made persistent, without changing their asymptotic query/update time? We present a (partially) persistent data structure that supports predecessor search in a set of integers in {1,...,U} under an arbitrary sequence of n insertions and deletions, with O(loglog U) expected query time and expected amortized update time, and O(n) space. The query bound is optimal in U for linear-space structures and improves previous near-O((loglog U)^2) methods.

The same method solves a fundamental problem from computational geometry: point location in orthogonal planar subdivisions (where edges are vertical or horizontal). We obtain the first static data structure achieving O(loglog U) worst-case query time and linear space. This result is again optimal in U for linear-space structures and improves the previous O((loglog U)^2) method by de Berg, Snoeyink, and van Kreveld (1992). The same result also holds for higher-dimensional subdivisions that are orthogonal binary space partitions, and for certain nonorthogonal planar subdivisions such as triangulations without small angles. Many geometric applications follow, including improved query times for orthogonal range reporting for dimensions >= 3 on the RAM.

Our key technique is an interesting new van-Emde-Boas-style recursion that alternates between two strategies, both quite simple.

- PDF file
- ACM Transactions on Algorithms, 9(3):22, 2013 (SODA special issue)
- In
*Proc. 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 1131-1145, 2011

We prove the existence of an algorithm A for computing 2-d or 3-d
convex hulls that is optimal for *every point set* in the
following sense: for every set S of n points and for every
algorithm A' in a certain class C, the maximum running time of
A on input s_1,...,s_n is at most a constant factor
times the maximum running time of A' on s_1,...,s_n,
where the maximum is taken over all permutations s_1,...,s_n of S.
In fact, we can establish a stronger property:
for every S and A', the maximum running time of A is at most a
constant factor times the average running time of A' over all
permutations of S. We call algorithms satisfying these properties
*instance-optimal* in the *order-oblivious* and
*random-order* setting. Such instance-optimal algorithms
simultaneously subsume output-sensitive algorithms and
distribution-dependent average-case algorithms, and all algorithms
that do not take advantage of the order of the input or that assume
the input is given in a random order.

The class C under consideration consists of all algorithms in a
decision tree model where the tests involve only *multilinear*
functions with a constant number of arguments. To establish an
instance-specific lower bound, we deviate from traditional
Ben-Or-style proofs and adopt an interesting adversary argument. For
2-d convex hulls, we prove that a version of the well known algorithm
by Kirkpatrick and Seidel (1986) or Chan,
Snoeyink, and Yap (1995)
already attains this lower bound. For 3-d convex hulls, we propose a
new algorithm.

To demonstrate the potential of the concept, we further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2-d and 3-d, orthogonal line segment intersection in 2-d, finding bichromatic L_infty-close pairs in 2-d, off-line orthogonal range searching in 2-d, off-line dominance reporting in 2-d and 3-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d.

- PostScript file (preliminary version)
- Journal of the ACM, 64(1): 3:1-3:38, 2017
- In
*Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS)*, pages 129-138, 2009

We reexamine fundamental problems from computational geometry in the word RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for offline point location, a two-dimensional analog of sorting where one needs to order points with respect to segments. This result implies, for example, that the Voronoi diagram of n points in the plane can be constructed in (randomized) time n . 2^{O(\sqrt{lg lg n})}. Similar bounds hold for numerous other geometric problems, such as three-dimensional convex hulls, planar Euclidean minimum spanning trees, line segment intersection, and triangulation of non-simple polygons.

In FOCS'06, we developed a data structure for
*online* point
location, which implied a bound of O(n lg n / lg lg n) for
Voronoi diagrams and the other problems. Our current bounds are
dramatically better, and a convincing improvement over the classic
O(n lg n) algorithms. As in the field of integer sorting, the main
challenge is to find ways to manipulate information, while avoiding
the online problem (in that case, predecessor search).

- arXiv version
- Submitted to
*ACM Transactions on Algorithms* - In
*Proc. 39th ACM Symposium on Theory of Computing (STOC)*, pages 31-39, 2007

Given a planar subdivision whose coordinates are integers bounded by U <= 2^w, we present a linear-space data structure that can answer point location queries in O(min{ lg n/lglg n, sqrt{lg U/lglg U} }) time on the unit-cost RAM with word size w. This is the first result to beat the standard Theta(lg n) bound for infinite precision models.

As a consequence, we obtain the first o(n lg n) (randomized) algorithms for many fundamental problems in computational geometry for arbitrary integer input on the word RAM, including: constructing the convex hull of a three-dimensional point set, computing the Voronoi diagram or the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments. Higher-dimensional extensions and applications are also discussed.

Though computational geometry with bounded precision input has been investigated for a long time, improvements have been limited largely to problems of an orthogonal flavor. Our results surpass this long-standing limitation, answering, for example, a question of Willard (SODA'92).

- PostScript file (journal version)
- SIAM Journal on Computing, 39:703-729, 2009 (FOCS special issue)
- The journal version combines my paper in Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS), pages 333-342, 2006 with Mihai's paper in Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS), pages 325-332, 2006

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 September 2018)