×

An optimal convex hull algorithm in any fixed dimension. (English) Zbl 0786.68091

This very interesting paper gives a solution to an outstanding problem in computational geometry. The author presents an deterministic algorithm for computing the convex hull of \(n\) points in any fixed dimension \(d\) in \(O(n \log n+n^{\lfloor d/2 \rfloor}) \) time. This algorithm is optimal in the worst case, but it is not output-sensitive. It is an open problem to bring down the complexity for this problem to the lower bound of \(\Omega (h+n \log h)\), where \(h\) is the facial complexity of the hull. The solution of the paper is based on a derandomizing-technique developed by the author. The counterpart of the algorithm given here is a probabilistic incremental method given in a known Las Vegas algorithm with optimal expected time.
The result of the paper seems to be the first example of a successfully derandomized Las Vegas incremental algorithm. The base is a deterministic version of a Monte Carlo integration method, which seems to be useful for other problems also. A by-product of the result is an algorithm for computing the Voronoi diagram of \(n\) points in \(d\)-space in the same optimal time.
Besides this results the author introduces the following ideas: 1. A scheme for producing “random-looking”-permutations. 2. An elementary error analysis to cope with faulty calculations in the Raghavan-Spencer method.
Reviewer: H.-D.Hecker (Jena)

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Agarwal, P. K. Partitioning arrangements of lines, I: An efficient deterministic algorithm,Discrete Comput. Geom.5 (1990), 449-483. · Zbl 0701.68035 · doi:10.1007/BF02187805
[2] Brown, K. Q. Voronoi diagrams from convex hulls,Inform. Process. Lett.9 (1979), 223-228. · Zbl 0424.68036 · doi:10.1016/0020-0190(79)90074-7
[3] Chazelle, B. Cutting hyperplanes for divide-and-conquer,Discrete Comput. Geom.9 (1993), 145-158. · Zbl 0784.52018 · doi:10.1007/BF02189314
[4] Chazelle, B., Friedman, J. A deterministic view of random sampling and its use in geometry,Combinatorica10 (1990), 229-249. · Zbl 0715.68036 · doi:10.1007/BF02122778
[5] Chazelle, B., Matoušek, J. Derandomizing an output-sensitive convex hull algorithm in three dimensions (submitted for publication). · Zbl 0814.68127
[6] Clarkson, K. L. A randomized algorithm for closest-point queries,SIAM J. Comput.17 (1988), 830-847. · Zbl 0651.68062 · doi:10.1137/0217052
[7] Clarkson, K. L. Randomized geometric algorithms, inEuclidean Geometry and Computers, D. Z. Du and F. K. Hwang, eds., World Scientific, to appear.
[8] Clarkson, K. L., Shor, P. W. Applications of random sampling in computational geometry, II,Discrete Comput. Geom.4 (1989), 387-421. · Zbl 0681.68060 · doi:10.1007/BF02187740
[9] Edelsbrunner, H.Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[10] Edelsbrunner, H., Seidel, R. Voronoi diagrams and arrangements,Discrete Comput. Geom.1 (1986), 25-44. · Zbl 0598.52013 · doi:10.1007/BF02187681
[11] Graham, R. L. An efficient algorithm for determining the convex hull of a planar point set,Inform. Process. Lett.1 (1972), 132-133. · Zbl 0236.68013 · doi:10.1016/0020-0190(72)90045-2
[12] Kirkpatrick, D. G., Seidel R. The ultimate planar convex hull algorithm?SIAM J. Comput.15 (1986), 287-299. · Zbl 0589.68035 · doi:10.1137/0215021
[13] Matoušek, J. Approximations and optimal geometric divide-and-conquer,Proc. 23rd Annual ACM Symp. on Theory of Computing, 1991, pp. 505-511.
[14] Matoušek, J. Efficient partition trees,Proc. 7th Annual ACM Symp. on Computational Geometry, 1991, pp. 1-9.
[15] Matoušek, J. Cutting hyperplane arrangements,Discrete Comput. Geom.6 (1991), 385-406. · Zbl 0765.68210 · doi:10.1007/BF02574697
[16] Matoušek, J. Linear optimization queries,J. Algorithms, to appear. · Zbl 0779.68089
[17] Preparata, F. P., Hong, S. J. Convex hulls of finite sets of points in two and three dimensions,Comm. ACM20 (1977), 87-93. · Zbl 0342.68030 · doi:10.1145/359423.359430
[18] Raghavan, P. Probabilistic construction of deterministic algorithms: approximating packing integer programs,J. Comput. System Sci.37 (1988), 130-143. · Zbl 0659.90066 · doi:10.1016/0022-0000(88)90003-7
[19] Seidel, R. A convex hull algorithm optimal for point sets in even dimensions, Technical Report 81-14, University of British Columbia, 1981.
[20] Seidel, R. Constructing higher-dimensional convex hulls at logarithmic cost per face,Proc. 18th Annual ACM Symp. on Theory of Computing, 1986, pp. 404-413.
[21] Seidel, R. Small-dimensional linear programming and convex hulls made easy,Discrete Comput. Geom.6 (1991), 423-434. · Zbl 0747.90066 · doi:10.1007/BF02574699
[22] Spencer, J.Ten Lectures on the Probabilistic Method, CBMS-NSF, SIAM, Philadelphia, PA, 1987. · Zbl 0703.05046
[23] Vapnik, V. N., Chervonenkis, A. Ya. On the uniform convergence of relative frequencies of events to their probabilities,Theory Probab. Appl.16 (1971), 264-280. · Zbl 0247.60005 · doi:10.1137/1116025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.