Timothy M. Chan's Publications: Output-sensitive/adaptive geometric algorithms

On constant factors in comparison-based geometric algorithms and data structures

(with Patrick Lee)

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:

Some of the results can be adapted to solve nonorthogonal problems, such as 2D convex hulls and general line segment intersection.

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.

Instance-optimal geometric algorithms

Peyman Afshani and Jérémy Barbay)

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.

Output-Sensitive Construction of Convex Hulls

(Ph.D. thesis,
Department of Computer Science, University of British Columbia, November 1995)

Optimal output-sensitive convex hull algorithms in two and three dimensions

We present simple output-sensitive algorithms that construct the convex hull of a set of n points in two or three dimensions in worst-case optimal O(n log h) time and O(n) space, where h denotes the number of vertices of the convex hull.

Output-sensitive results on convex hulls, extreme points, and related problems

We use known data structures for ray shooting and linear programming queries to derive new output-sensitive results on convex hulls, extreme points, and related problems. We show that the f-face convex hull of an n-point set P in a fixed dimension d >= 2 can be constructed in O(n log f + (nf)^{1-1/(floor(d/2)+1)} polylog n) time; this is optimal if f = O(n^{1/floor(d/2)} / log^K n) for some sufficiently large constant K. We also show that the h extreme points of P can be computed in O(n polylog h + (nh)^{1-1/(floor(d/2)+1)} polylog n) time. These results are then applied to produce an algorithm that computes the vertices of all the convex layers of P in O(n^{2-gamma}) time for any constant gamma < 2/((floor(d/2))^2+1). Finally, we obtain improved time bounds for other problems including levels in arrangements and linear programming with few violated constraints. In all of our algorithms, the input is assumed to be in general position.

Primal dividing and dual pruning: output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams

Jack Snoeyink, and Chee-Keng Yap)

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.

Copyright Notice

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)