@techreport{Clarkson77, author = {K. L. Clarkson}, title = {Implementation of a Model of ${\rm CO}_2$ Diffusion in the Midtroposphere}, type = {Claremont Graduate School Technical Report}, address = {Claremont, CA}, year = {1977} } @inproceedings{Clarkson81, author = {K. L. Clarkson}, title = {A Procedure for Camera Calibration}, booktitle = {Proceedings of the DARPA Image Understanding Workshop}, address = {Maclean, VA: Science Applications, Inc.}, year = {1981}, } @article{Clarkson82, author = {K. L. Clarkson}, editor = {P. Cohen and E. Feigenbaum (eds) and Kaufman, Inc.,, W.}, title = {Grammatical Inference}, journal = {The Handbook of Artificial Intelligence}, volume = {3}, address = {Los Altos, CA}, year = {1982}, } @article{Clarkson83, author = {K. L. Clarkson}, title = {A Modification of the Greedy Algorithm for Vertex Cover}, journal = {Information Processing Letters}, volume = {16}, pages = {23--25}, month = {January}, year = {1983} } @inproceedings{2-ann, author = {K. L. Clarkson}, title = {Fast Algorithms for the All Nearest Neighbors Problem}, booktitle = {Proc. 24th Symp. on Foundations of Computer Science}, address = {Tucson, AZ}, month = {November}, year = {1983} , abstract ={ We present new algorithms for the {\it all nearest neighbors\/} problem: \narrow Given a set $S$ of $n$ sites (points) in $d$-dimensional space, find the nearest neighbors in set $S$ of each site in~$S$. \endnarrow Our results: \begintick \tick An algorithm for solving the all nearest neighbors problem in $O(n\log\sigma)$ time, where $\sigma$ is the ratio of the distance between the farthest pair of sites to the distance between the closest pair of sites. A similar algorithm is described for finding all $k$'th nearest neighbors. \tick An algorithm for building a {\it celltree}, a compressed form of digital trie, in $O(n\log n)$ probabilistic time. The logarithm, floor, and bitwise exclusive-or functions are assumed available at unit cost. \tick An algorithm for solving the all nearest neighbors problem in $O(n)$ worst-case time, given a celltree for the sites. \tick An algorithm for building a celltree in linear expected time, assuming the sites are independently identically distributed random variables, with an unknown probability density function obeying some very weak conditions. \endtick } } @inproceedings{Clarkson84, author = {K. L. Clarkson}, title = {Fast Expected-time and Approximation Algorithms for Geometric Minimum Spanning Trees}, booktitle = {Proc. 16th Annual SIGACT Symposium}, address = {Washington, DC}, month = {April}, year = {1984} } @phdthesis{Clarkson85, author = {K. L. Clarkson}, title = {Algorithms for Closest-point Problems}, school = {Stanford University}, month = {January}, year = {1985} } @article{2-po, author = {K. L. Clarkson}, title = {A Randomized Algorithm for Closest-Point Queries}, journal = sicomp, year = {1988}, pages = {830-847}, appearedin = {Proc. 17th Annual SIGACT Symposium}, ayear = {1985} , url = {http://cm.bell-labs.com/cm/cs/doc/88/2-po.ps.gz} , abstract ={ An algorithm for closest-point queries is given. The problem is this: given a set $S$ of $n$ points in $d$-dimensional space, build a data structure so that given an arbitrary query point~$p$, a closest point in $S$ to $p$ can be found quickly. The measure of distance is the Euclidean norm. This is sometimes called the {\em post-office problem}. %\cite{Kn}. The new data structure will be termed an {\em RPO tree}, from Randomized Post Office. The expected time required to build an RPO tree is $O(n^{\dvtc (1+ \epsilon )} )$, for any fixed $\epsilon > 0$, and a query can be answered in $O(\log n )$ worst-case time. An RPO tree requires $O(n^{\dvtc (1+ \epsilon )} )$ space in the worst case. The constant factors in these bounds depend on $d$ and $\epsilon$. The bounds are average-case due to the randomization employed by the algorithm, and hold for any set of input points. This result approaches the $\Omega(n^\dvtc )$ worst-case time required for any algorithm that constructs the Voronoi diagram of the input points, and is a considerable improvement over previous bounds for $d>3$. The main step of the construction algorithm is the determination of the Voronoi diagram of a random sample of the sites, and the triangulation of that diagram. } } @article{Clarkson86, author = {K. L. Clarkson}, title = {Linear Programming in $0(n3^{d^2})$ Time}, journal = {Information Processing Letters}, volume = {22}, pages = {21--24}, month = {January}, year = {1986} } @article{rs, author = {K. L. Clarkson}, title = {New Applications of Random Sampling to Computational Geometry}, journal = {Discrete and Computational Geometry}, volume = {2}, pages = {195--222}, year = {1987}, appearedas = {Further Applications of Random Sampling to Computational Geometry}, appearedin = {Proc. 18th Annu. ACM Sympos. Theory Comput.}, ayear = {1986} , url = {http://cm.bell-labs.com/cm/cs/doc/86/2-rs.ps.gz} , abstract ={ This paper gives several new demonstrations of the usefulness of random sampling techniques in computational geometry. One new algorithm creates a search structure for arrangements of hyperplanes by sampling the hyperplanes and using information from the resulting arrangement to divide and conquer. This algorithm requires \({O(s ^ {d + \epsilon})}\) expected preprocessing time to build a search structure for an arrangement of $s$ hyperplanes in $d$ dimensions. The expectation, as with all expected times reported here, is with respect to the random behavior of the algorithm, and holds for any input. Given the data structure, and a query point $p$, the cell of the arrangement containing $p$ can be found in \({O( \log s)}\) worst-case time. (The bound holds for any fixed \({\epsilon >0}\), with the constant factors dependent on $d$ and $\epsilon$.) Using point-plane duality, the algorithm may be used for answering halfspace range queries. Another algorithm finds random samples of simplices to determine the separation distance of two polytopes. The algorithm uses expected \({O(n ^\dvtf )}\) time, where $n$ is the total number of vertices of the two polytopes. This matches previous results \cite{DoK} for the case $d=3$ and extends them. Another algorithm samples points in the plane to determine their order $k$ Voronoi diagram, and requires expected \({O(s^{1+\epsilon}k)}\) time for $s$ points. (It is assumed that no four of the points are cocircular.) This sharpens the bound \({O(sk ^ 2 \log s)}\) for Lee's algorithm \cite{Lee}, and \({O(s ^ 2 \log s + k(s-k) \log ^ 2 s)}\) for Chazelle and Edelsbrunner's algorithm \cite{ChE}. Finally, random sampling is used to show that any set of $s$ points in $E^3$ has \({O(sk^2\log ^ 8 s / ( \log \log s) ^ 6 )}\) distinct $j$-sets with $j\leq k$. (For $S \subset \Ed$, a set $S'\subset S$ with $|S'|=j$ is a $j$-set of $S$ if there is a halfspace $h^+$ with $S'=S \cap h^+$.) This sharpens with respect to $k$ the previous bound \({O(s k ^ 5 )}\) \cite{ChP}. The proof of the bound given here is an instance of a ``probabilistic method''~\cite{ErS}. } } @article{Guibas87, author = {L. J. Guibas and J. Stolfi and K. L. Clarkson}, title = {Solving Related Two and Three Dimensional Linear Programming Problems in Logarithmic Time}, journal = {Theoretical Computer Science}, volume = {49}, pages = {81--84}, year = {1987} } @inproceedings{mp, author = {K. L. Clarkson}, title = {Approximation Algorithms for Shortest Path Motion Planning}, booktitle = {Proc. 19th Annual SIGACT Symposium}, address = {New York, New York}, month = {May}, year = {1987} , url = {http://cm.bell-labs.com/cm/cs/doc/87/2-mp.ps.gz} , abstract ={ This paper gives approximation algorithms for solving the following motion planning problem: Given a set of polyhedral obstacles and points $s$ and~$t$, find a shortest path from $s$ to~$t$ that avoids the obstacles. The paths found by the algorithms are piecewise linear, and the length of a path is the sum of the lengths of the line segments making up the path. Approximation algorithms will be given for versions of this problem in the plane and in three-dimensional space. The algorithms return an $\epsilon$-short path, that is, a path with length within $(1+\epsilon)$ of shortest. Let $n$ be the total number of faces of the polyhedral obstacles, and $\epsilon$ a given value satisfying $0<\epsilon\leq\pi$. The algorithm for the planar case requires $O(n\log n)/\epsilon$ time to build a data structure of size $O(n/\epsilon)$. Given points $s$ and~$t$, an $\epsilon$-short path from $s$ to $t$ can be found with the use of the data structure in time $O(n/\epsilon+n\log n)$. The data structure is associated with a new variety of Voronoi diagram. Given obstacles $S\subset E^3$ and points $s,t\in E^3$, an $\epsilon$-short path between $s$ and $t$ can be found in \[O(n^2\lambda(n)\log(n/\epsilon)/\epsilon^4+n^2\log n\rho\log(n\log \rho))\] time, where $\rho$ is the ratio of the length of the longest obstacle edge to the distance between $s$ and $t$. The function $\lambda(n)=\alpha(n)^{O(\alpha(n)^{O(1)})}$, where the $\alpha(n)$ is a form of inverse of Ackermann's function. For $\log(1/\epsilon)$ and $\log\rho$ that are $O(\log n)$, this bound is $O(n^2(\log^2n)\lambda(n)/\epsilon^4)$. } } @inproceedings{l1mp, author = {K. L. Clarkson and S. Kapoor and P. Vaidya}, title = {Rectilinear Shortest Paths through Polygonal Obstacles in ${O}(n \log^2 n)$ Time}, booktitle = {Proc. Third Annual Symposium on Computational Geometry}, address = {Waterloo, Ontario}, month = {June}, year = {1987} , url = {http://cm.bell-labs.com/cm/cs/doc/87/2-l1mp.ps.gz} , abstract ={ The problem of finding a rectilinear shortest path amongst obstacles may be stated as follows: Given a set of obstacles in the plane find a shortest rectilinear ($L sub 1$) path from a point $s$ to a point $t$ which avoids all obstacles. The path may touch an obstacle but may not cross an obstacle. We study the rectilinear shortest path problem for the case where the obstacles are non-intersecting simple polygons, and present an $O( n^( log n ) sup 2 )$ algorithm for finding such a path, where $n$ is the number of vertices of the obstacles. This algorithm requires $O(n log n )$ space. Another algorithm is given that requires $O(n ( log n ) sup 3/2 )$ time and space. We also study the case of rectilinear obstacles in three dimensions, and show that $L sub 1$ shortest paths can be found in $O( n sup 2 ^( log~n ) sup 3 )$ time. } } @article{Clarkson89, author = {K. L. Clarkson}, title = {An Algorithm for Geometric Minimum Spanning Trees Requiring Nearly Linear Expected Time}, journal = {Algorithmica}, volume = {4}, pages = {461--469}, year = {1989} } @inproceedings{Clarkson88, author = {K. L. Clarkson}, title = {Applications of Random Sampling in Computational Geometry, {II}.}, booktitle = {Proc. Fourth Annual Symposium on Computational Geometry}, address = {Urbana, Illinois}, month = {June}, year = {1988} } @inproceedings{Clarkson88a, author = {K. L. Clarkson and P. W. Shor}, title = {Algorithms for Diametral Pairs and Convex Hulls that are Optimal, Randomized, and Incremental.}, booktitle = {Proc. Fourth Annual Symposium on Computational Geometry}, address = {Urbana, Illinois}, month = {June}, year = {1988} } @article{rs2m, author = {K. L. Clarkson and P. W. Shor}, title = {Applications of Random Sampling in Computational Geometry, {II}.}, journal = {Discrete and Computational Geometry}, volume = {4}, number = {1}, pages = {387--421}, year = {1989}, note = {(Merges two papers above.)} , url = {http://cm.bell-labs.com/cm/cs/doc/88/2-rs2m.ps.gz} , abstract ={ We use random sampling for several new geometric algorithms. The algorithms are ``Las Vegas,'' and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requires $O(A+n\log n)$ expected time, where~$A$ is the number of intersecting pairs reported. The algorithm requires $O(n)$ space in the worst case. Another algorithm computes the convex hull of $n$ points in $E^d$ in $O(n\log n)$ expected time for $d=3$, and $O(n^\dvtf)$ expected time for $d>3$. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set of $n$ points in $E^3$ in $O(n\log n)$ expected time, and on the way computes the intersection of $n$ unit balls in $E^3$. We show that $O(n\log A)$ expected time suffices to compute the convex hull of $n$ points in $E^3$, where $A$ is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for $(\lee k)$-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high order Voronoi diagrams. } } @article{Clarkson89b, author = {K. L. Clarkson and R. E. Tarjan and C. J. Van Wyk}, title = {A Fast Las Vegas Algorithm for Triangulating a Simple Polygon}, journal = {Discrete and Computational Geometry}, volume = {4}, number = {1}, pages = {423--432}, year = {1989}, appearedin = {Proc. Fourth Annual Symposium on Computational Geometry}, ayear = {1988} } @inproceedings{lp2, author = {K. L. Clarkson}, title = {A {L}as {V}egas algorithm for linear programming when the dimension is small}, booktitle = {Proc. 29th Annual IEEE Symposium on Foundations of Computer Science}, pages = {452--456}, month = {October}, year = {1988}, note = {Revised version: Las Vegas algorithms for linear and integer programming when the dimension is small, to appear in J. ACM.} , url = {http://cm.bell-labs.com/cm/cs/doc/2-lp2.ps.gz} , abstract ={ This paper gives an algorithm for solving linear programming problems. For a problem with $n$ constraints and $d$ variables, the algorithm requires an expected \[O(d^2n)+(\log n)O(d)^{d/2+O(1)}+O(d^4\sqrt{n}\log n)\] arithmetic operations, as $n\rightarrow\infty$. The constant factors do not depend on~$d$. Also, an algorithm is given for integer linear programming. Let $\varphi$ bound the number of bits required to specify the rational numbers defining an input constraint or the objective function vector. Let $n$ and $d$ be as before. Then the algorithm requires expected \[O(2^ddn+8^dd\sqrt{n\ln n}\ln n)+d^{O(d)}\varphi\ln n\] operations on numbers with $d^{O(1)}\varphi$ bits, as $n\ra\infty$, where the constant factors do not depend on $d$ or $\varphi$. The expectations are with respect to the random choices made by the algorithms, and the bounds hold for any given input. The technique can be extended to other convex programming problems. For example, an algorithm for finding the smallest sphere enclosing a set of $n$ points in $E^d$ has the same time bound. } } @article{BCL, author = {J. L. Bentley and K. L. Clarkson and D. B. Levine}, title = {Fast Linear Expected-Time Algorithms for Computing Maxima and Convex Hulls}, journal = {Algorithmica}, pages = {168-183}, year = {1993}, appearedin = {Proc. 1st Annual ACM-SIAM Symposium on Discrete Algorithms}, ayear= {1990} } @article{Clarkson90, author = {K. L. Clarkson and H. Edelsbrunner and L. Guibas and M. Sharir and E. Welzl}, title = {Combinatorial complexity bounds for arrangements of curves and surfaces}, journal = {Discrete and Computational Geometry}, volume = {5}, number = {2}, pages = {99--160}, year = {1990}, appearedin = {Proc. 29th Annual IEEE Symposium on Foundations of Computer Science}, ayear = {1988} } @inproceedings{tsp, author = {K. L. Clarkson}, title = {Approximation algorithms for planar traveling salesman tours and minimum-length triangulations}, booktitle = {Proc. Second ACM Symposium on Discrete Algorithms}, month = {January}, year = {1991} , url = {http://cm.bell-labs.com/cm/cs/doc/91/2-tsp.ps.gz} , abstract ={ This paper gives a partitioning scheme for the geometric, planar traveling salesman problem, under the Euclidean metric: given a set $S$ of $n$ points in the plane, find a shortest closed tour (path) visiting all the points. The scheme employs randomization, and gives a tour that can be expected to be short, if $S$ satisfies the condition that a random subset $R\subset S$ has on average a tour much shorter than an optimal tour of $S$. This condition holds for points independently, identically distributed in the plane, for example, for which a tour within $1+\epsilon$ of shortest can be found in expected time $nk^2 2^k$, where $k=O(\log\log n)^3/\epsilon^2$. One algorithm employed in the scheme is of interest in its own right: when given a simple polygon $P$, it finds a Steiner triangulation of the interior of~$P$. If $P$ has $n$ sides and perimeter $L_P$, the edges of the triangulation have total length $L_PO(\log n)$. If this algorithm is applied to a simple polygon induced by a minimum spanning tree of a point set, the result is a Steiner triangulation of the set with total length within a factor of $O(\log n)$ of the minimum possible. } } @article{tri, author = {K. L. Clarkson and R. Cole and R. E. Tarjan}, title = {Randomized parallel algorithms for trapezoidal diagrams}, journal = {Int. J. Comp. Geom. and Applications}, year = {1992}, pages = {117-133}, appearedin = {Proc. Seventh Annual Symposium on Computational Geometry}, ayear = {1991} , url = {http://cm.bell-labs.com/cm/cs/doc/92/2-tri.ps.gz} , abstract ={ We describe randomized parallel algorithms for building trapezoidal diagrams of line segments in the plane. The algorithms are designed for a CRCW PRAM. For general segments, we give an algorithm requiring optimal $O(A+n\log n)$ expected work and optimal $O(\log n)$ time, where $A$ is the number of intersecting pairs of segments. If the segments form a simple chain, we give an algorithm requiring optimal $O(n)$ expected work and $O(\log n\log\log n\log^*n)$ expected time\footnotemark, and a simpler algorithm requiring $O(n\log^*n)$ expected work. The serial algorithm corresponding to the latter is among the simplest known algorithms requiring $O(n\log^*n)$ expected operations. For a set of segments forming $K$ chains, we give an algorithm requiring $O(A+n\log^*n+K\log n)$ expected work and $O(\log n\log\log n\log^*n)$ expected time. The parallel time bounds require the assumption that enough processors are available, with processor allocations every $\log n$ steps. } } @article{4res, author = {K. L. Clarkson and K. Mehlhorn and R. Seidel}, title = {Four results on randomized incremental constructions}, journal = {Comp. Geom.: Theory and Applications}, year = {1993}, pages = {185-121}, appearedin={Proc. Symp. Theor. Aspects of Comp. Sci.}, ayear = {1992} , url = {http://cm.bell-labs.com/cm/cs/doc/93/2-4res.ps.gz} , abstract ={ \noindent We prove four results on randomized incremental constructions (RICs): \begin{itemize} \item an analysis of the expected behavior under insertion and deletions, \item a fully dynamic data structure for convex hull maintenance in arbitrary dimensions, \item a tail estimate for the space complexity of RICs, \item a lower bound on the complexity of a game related to RICs. \end{itemize} } } @article{rga, author = {K. L. Clarkson}, editor = {F. K. Hwang and D. Z. Hu (eds) and World Scientific Publishing}, title = {Randomized Geometric Algorithms}, journal = {Computers and Euclidean Geometry}, year = {1992} , url = {http://cm.bell-labs.com/cm/cs/doc/92/2-rga.ps.gz} , abstract ={ This paper surveys some of the applications of randomization to computational and combinatorial geometry. Randomization provides a general way to divide-and-conquer geometric problems, and gives a simple incremental approach to building geometric structures. The paper discusses closest-point problems, convex hulls, Voronoi diagrams, trapezoidal diagrams of line segments, linear programming in small dimension, range queries, and bounds for point-line incidences and for $(\lee k)$-sets. Relations to the Vapnik-Chervonenkis dimension, PAC-learnability of geometric concepts, and the Hough transform are briefly noted. } } @article{kmins, author = {K. L. Clarkson}, title = {A bound on local minima of arrangements that implies the upper bound theorem}, journal = {Discrete and Computational Geometry}, volume = {10}, pages = {427--233}, year = {1993} , url = {http://cm.bell-labs.com/cm/cs/doc/92/2-07.ps.gz} , abstract ={ This paper shows that the $i$-level of an arrangement of hyperplanes in $E^d$ has at most ${{i+d-1}\choose {d-1}}$ local minima. This bound follows from ideas previously used to prove bounds on $(\lee k)$-sets. Using linear programming duality, the Upper Bound Theorem is obtained as a corollary, giving yet another proof of this celebrated bound on the number of vertices of a simple polytope in $E^d$ with $n$ facets. } } @inproceedings{dets, author = {K. L. Clarkson}, title = {Safe and effective determinant evaluation}, booktitle = {Proc. 31st IEEE Symposium on Foundations of Computer Science}, address = {Pittsburgh, PA}, month = {October}, year = {1992}, pages = {387-395} , url = {http://cm.bell-labs.com/cm/cs/doc/92/2-dets.ps.gz} , abstract ={ The problem of evaluating the sign of the determinant of a small matrix arises in many geometric algorithms. Given an $n\times n$ matrix $A$ with integer entries, whose columns are all smaller than $M$ in Euclidean norm, the algorithm given here evaluates the sign of the determinant $\det A$ exactly. The algorithm requires an arithmetic precision of less than $1.5n+2\lg M$ bits. The number of arithmetic operations needed is $O(n^3)+O(n^2)\log\OD(A)/\beta$, where $\OD(A)|\det A|$ is the product of the lengths of the columns of $A$, and $\beta$ is the number of ``extra'' bits of precision, \[\textstyle \min\{\lg(1/\bu)-1.1n-2\lg n-2,\lg N - \lg M - 1.5n - 1\},\] where $\bu$ is the roundoff error in approximate arithmetic, and $N$ is the largest representable integer. Since $\OD(A)\leq M^n$, the algorithm requires $O(n^3\lg M)$ time, and $O(n^3)$ time when $\beta=\Omega(\log M)$. } } @inproceedings{center, author = {K. L. Clarkson and D. Eppstein and G. L. Miller and C. Sturtivant and S. Teng}, title = {Approximating center points with iterated Radon points}, booktitle = {Proceedings of the 9th acm Symposium on Computational Geometry}, address = {San Diego, CA}, year = {1993}, toappear = {Internat. J. Comput. Geom. Appl.} , url = {http://cm.bell-labs.com/cm/cs/doc/93/2-12.ps.gz} , abstract ={ We give a practical and provably good Monte Carlo algorithm for approximating center points. Let $P$ be a set of $n$ points in $\R^d$. A point $c \in \R^d$ is a $\beta$-center point of $P$ if every closed halfspace containing $c$ contains at least $\beta n$ points of $P$. Every point set has a $1/(d+1)$-center point; our algorithm finds an $\Omega(1/d^2)$-center point with high probability. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in $d$. Moreover, it can be optimally parallelized to require $O(\log^2d\log\log n)$ time. Our algorithm has been used in mesh partitioning methods and can be used in constructing high breakdown estimators for multivariate datasets in statistics. It has the potential to improve results in practice for constructing weak $\epsilon$-nets. We derive a variant of our algorithm whose time bound is fully polynomial in~$d$ and linear in~$n$, and show how to combine our approach with previous techniques to compute high quality center points more quickly. } } @inproceedings{Clarkson93b, author = {K. L. Clarkson}, title = {Algorithms for polytope covering and approximation}, booktitle = {Proc. 3rd Workshop on Algorithms and Data Structures}, pages = {246--252}, year = {1993} } @inproceedings{Clarkson94, author = {K. L. Clarkson}, title = {An algorithm for approximate closest-point queries}, booktitle = {Proc. Tenth Annual Symposium on Computational Geometry}, year = {1994}, pages = {160-164} } @unpublished{pcover , author = "K. L. Clarkson" , title = {Algorithms for Polytope Covering and Approximation, and for Approximate Closest-point Queries} , year = {1994} , note = {(Merges two papers above)} , url = {http://cm.bell-labs.com/cm/cs/doc/94/2-04.ps.gz} , abstract ={ This paper gives an algorithm for {\em polytope covering}\/: let $L$ and $U$ be sets of points in $R^d$, comprising $n$ points altogether. A {\em cover} for $L$ from $U$ is a set $C\subset U$ with $L$ a subset of the convex hull of $C$. Suppose $c$ is the size of a smallest such cover, if it exists. The randomized algorithm given here finds a cover of size no more than $c(\rboundp)$, for $c$ large enough. The algorithm requires $O(c^2n^{1+\delta})$ expected time.\footnote{In this paper, $\delta$ will denote any fixed value greater than zero.} More exactly, the time bound is \[O(cn^{1+\delta}+c(nc)^{1/(1+\gamma/(1+\delta))}),\] where $\gamma\equiv 1/\dvtf$. The previous best bounds were $cO(\log n)$ cover size in $O(n^d)$ time.\cite{MiS} A variant algorithm is applied to the problem of approximating the boundary of a polytope with the boundary of a simpler polytope. For an appropriate measure, an approximation with error $\epsilon$ requires $c=O(1/\epsilon)^{(d-1)/2}$ vertices, and the algorithm gives an approximation with $c(\apboundp)$ vertices. The algorithms apply ideas previously used for small-dimensional linear programming. The final result here applies polytope approximation to the the {\em post office problem}: given $n$ points (called sites) in $d$ dimensions, build a data structure so that given a query point $q$, the closest site to $q$ can be found quickly. The algorithm given here is given also a relative error bound $\epsilon$, and depends on a ratio $\rho$, which is no more than the ratio of the distance between the farthest pair of sites to the distance between the closest pair of sites. The algorithm builds a data structure of size $O(n(\log\rho)/\epsilon^{d/2}$ in time $O(n^2(\log\rho))/\epsilon^d$. With this data structure, closest-point queries can be answered in $O(\log n)/\epsilon^{d/2}$ time. } } @inproceedings{os , author = "K. L. Clarkson" , title = "More output-sensitive geometric algorithms" , booktitle = "Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci." , year = 1994 , pages = "695--702" , update = "95.01 matousek+smid" , url = {http://cm.bell-labs.com/cm/cs/doc/94/2-13.ps.gz} , abstract = { A simple idea for speeding up the computation of extrema of a partially ordered set turns out to have a number of interesting applications in geometric algorithms; the resulting algorithms generally replace an appearance of the input size $n$ in the running time by an output size $A\leq n$. In particular, the $A$ coordinate-wise minima of a set of $n$ points in $R^d$ can be found by an algorithm needing $O(nA)$ time. Given $n$ points uniformly distributed in the unit square, the algorithm needs $n+O(n^{5/8})$ point comparisons on average. Given a set of $n$ points in $R^d$, another algorithm can find its $A$ extreme points in $O(nA)$ time. Thinning for nearest-neighbor classification can be done in time $O(n\log n)\sum_i A_in_i$, finding the $A_i$ irredundant points among $n_i$ points for each class $i$, where $n=\sum_i n_i$ is the total number of input points. This sharpens a more obvious $O(n^3)$ algorithm, which is also given here. Another algorithm is given that needs $O(n)$ space to compute the convex hull of $n$ points in $O(nA)$ time. Finally, a new randomized algorithm finds the convex hull of $n$ points in $O(n\log A)$ expected time, under the condition that a random subset of the points of size $r$ has expected hull complexity $O(r)$. All but the last of these algorithms has polynomial dependence on the dimension~$d$, except possibly for linear programming. } } @inproceedings{os , author = "K. L. Clarkson" , title = "Nearest Neighbor Queries in Metric Spaces" , booktitle = "Proc. 29th Symp. Theory Comput." , year = 1997 , url = {http://cm.bell-labs.com/cm/cs/doc/97/4-1.ps.gz} , abstract = { Given a set $S$ of $n$ sites (points), and a distance measure $d$, the {\em nearest neighbor searching} problem is to build a data structure so that given a query point $q$, the site nearest to $q$ can be found quickly. This paper gives data structures for this problem when the sites and queries are in a metric space. The data structures can be analyzed when the metric space satisfies a certain sphere-packing bound. One data structure, denoted $D(S)$, requires expected $O(n)(\lg n)^{O(\lg\lg\Upsilon(S))}$ time to build. Here $\Upsilon(S)$ is the {\em distance ratio} of $S$, the ratio of the distance between the farthest pair of points in $S$ to the distance between the closest pair. The constant factors in the bound depend on the sphere-packing bound. When the query point $q$ is a random element of $\{q\}\cup S$, as for example when $q$ and the points of $S$ are randomly generated from a common distribution, then the query time is expected $(\lg n)^{O(\lg\lg\Upsilon(S))}$. A side effect of building $D(S)$ is to solve the all-nearest-neighbors problem for~$S$. Another data structure given here, denoted $M(S,Q)$, requires as input data an additional set $Q$, taken to be representative of the query points. The data structure $M(S,Q)$ can sometimes return wrong answers, but when $q$ is a random element of $\{q\}\cup Q$, the probability of failure is $O(\log^2n)/K$, where $K\leq |Q|/n$ is a parameter of the construction. When $S$ is a random subset of $S\cup Q$, $M(S,Q)$ can be built in expected $O(Kn(\log n)^2(\log\Upsilon\log n\Upsilon)$ time. Here $\Upsilon$ is the distance ratio for $S\cup Q$. When $S$ and $\{q\}$ are random subsets of $\{q\}\cup Q\cup S$, the expected query time for $M(S,Q)$ is $O(K\log n)\log\Upsilon$, when the returned answer is correct. The expected space needed is $O(n)K\log\Upsilon$. } }