Author :
Afshani, Peyman ; Barbay, Jérémy ; Chan, Timothy M.
Author_Institution :
Center for Massive Data Algorithmics, Univ. of Aarhus, Aarhus, Denmark
Abstract :
We prove the existence of an algorithm A for computing 2-d or 3-dconvex 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 A, the running time of A on the worst permutation of S for A is at most a constant factor times the running time of A´ on the worst permutation of S for A´. In fact, we can establish a stronger property: for every S and A´, the running time of A on S 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 A 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. 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, offline orthogonal range searching in 2-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d. The theory we develop also neatly reveals connections to entropy-dependent data structures, and yields as a byproduct new expected case results, e.g., for on-line orthogonal range counting in 2-d.
Keywords :
computational geometry; convex programming; decision trees; geometric programming; 2d convex hulls; 3d convex hulls; computational geometry; decision tree model; distribution-dependent average-case algorithms; entropy-dependent data structures; instance-optimal geometric algorithms; multilinear functions; off-line halfspace range reporting; off-line orthogonal range searching; off-line point location; on-line orthogonal range; orthogonal line segment intersection; output-sensitive algorithms; random-order setting; Adaptive algorithm; Computational geometry; Computational modeling; Computer science; Costs; Data structures; Decision trees; Size measurement; Testing; Tree data structures; adaptive algorithms; computational geometry; convex hull; decision trees; entropy-sensitive data structures; instance optimality; lower bounds; maxima; orthogonal segment intersection; output-sensitive algorithms; point location;