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 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

- Gzipped postscript file
- Combines papers:

- Postscript file
- Discrete & Computational Geometry, 16:361-368, 1996 (SoCG special issue)

- Postscript file
- Discrete & Computational Geometry, 16:369-387, 1996 (SoCG special issue)
- Preliminary version in Proc. 11th ACM Symposium on Computational Geometry (SoCG), pages 10-19, 1995
- Specialization of results to 2-d and 3-d in separate paper

In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E^4. Our algorithm runs in O((n+f) log^2 f) time and uses O(n+f) space. This is the first algorithm within a polylogarithmic factor of optimal O(n log f + f) time over the whole range of f. By a standard lifting map, we obtain output-sensitive algorithms for the Voronoi diagram or Delaunay triangulation in E^3 and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the "ultimate convex hull algorithm" of Kirkpatrick and Seidel in E^2 and also leads to improved output-sensitive results on constructing convex hulls in E^d for any even constant d > 4.

- Postscript file
- Discrete & Computational Geometry, 18:433-454, 1997
- Preliminary "dual" version in Proc. 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 282-291, 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 2021)