Discrete & Computational Geometry

, Volume 16, Issue 4, pp 369–387

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

• T. M. Chan
Article

## Abstract

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 thef-face convex hull of ann-point setP in a fixed dimensiond≥2 can be constructed in$$0\left( {n log f + \left( {nf} \right)^{1 - 1/\left( {\left[ {d/2} \right] + 1} \right)} \log ^{0\left( 1 \right)} n} \right)$$ time; this is optimal if$$f = 0\left( {n^{1/\left[ {d/2} \right]} /\log ^K n} \right)$$ for some sufficiently large constantK. We also show that theh extreme points ofP can be computed in$$0\left( {n log^{0\left( 1 \right)} h + \left( {nh} \right)^{1 - 1/\left( {\left[ {d/2} \right] + 1} \right)} \log ^{0\left( 1 \right)} n} \right)$$ time. These results are then applied to produce an algorithm that computes the vertices of all the convex layers ofP inO(n 2−γ) time for any constant$$\gamma< 2/\left( {\left[ {d/2} \right]^2 + 1} \right)$$. 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.

## Keywords

Convex Hull Extreme Point Voronoi Diagram Query Time Convex Hull Algorithm
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. 1.
P. K. Agarwal and J. Matoušek. Ray shooting and parametric search.SIAM J. Comput., 22:794–806, 1993.
2. 2.
P. K. Agarwal and J. Matoušek. Dynamic half-space range reporting and its applications.Algorithmica, 13:325–345, 1995.
3. 3.
J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson. On the average number of maxima in a set of vectors.J. Assoc. Comput. Mach., 25:536–543, 1978.
4. 4.
J. L. Bentley and J. Saxe. Decomposable searching problems, I: static-to-dynamic transformations.J. Algorithms, 1:301–358, 1980.
5. 5.
T. M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems.Proc. 11th ACM Symp. on Computational Geometry, pp. 10–19, 1995.Google Scholar
6. 6.
T. M. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions.Discrete Comput. Geom., this issue, pp. 361–368.Google Scholar
7. 7.
T. M. Chan, J. Snoeyink, and C.-K. Yap. Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three.Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, pp. 282–291, 1995.Google Scholar
8. 8.
D. R. Chand and S. S. Kapur. An algorithm for convex polytopes.J. Assoc. Comput. Mach., 17:78–86, 1970.
9. 9.
B. Chazelle. An optimal algorithm for computing convex layers.IEEE Trans. Inform. Theory, 31:509–517, 1985.
10. 10.
B. Chazelle. An optimal convex hull algorithm for point sets in any fixed dimension.Discrete Comput. Geom., 9:145–158, 1993.
11. 11.
B. Chazelle and J. Matoušek. Derandomizing an output-sensitive convex hull algorithm in three dimensions.Comput. Geom. Theory Appl., 5:27–32, 1995.
12. 12.
K. L. Clarkson. More output-sensitive geometric algorithms.Proc. 35th IEEE Symp. on Foundations of Computer Science, pp. 695–702, 1994.Google Scholar
13. 13.
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom., 4:387–421, 1989.
14. 14.
R. Cole. Slowing down sorting networks to obtain faster sorting algorithms.J. Assoc. Comput. Mach., 34:200–208, 1987.
15. 15.
D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection.Theoret. Comput. Sci., 27:241–253, 1983.
16. 16.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin, 1987.
17. 17.
H. Edelsbrunner and E. P. Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms.ACM Trans. Graphics, 9:66–104, 1990.
18. 18.
H. Edelsbrunner and E. Shi. AnO(n log2 h) time algorithm for the three-dimensional convex hull problem.SIAM J. Comput., 20:259–277, 1991.
19. 19.
H. Edelsbrunner and E. Welzl. Constructing belts in two-dimensional arrangements with applications.SIAM J. Comput., 15:271–284, 1986.
20. 20.
I. Emiris and J. Canny. An efficient approach to removing geometric degeneracies.Proc. 8th ACM Symp. on Computational Geometry, pp. 74–82, 1992.Google Scholar
21. 21.
D. Eppstein. Dynamic three-dimensional linear programming.Proc. 32nd IEEE Symp. on Foundations of Computer Science, pp. 488–494, 1991.Google Scholar
22. 22.
R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set.Inform. Process. Lett., 1:132–133, 1972.
23. 23.
D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm?SIAM J. Comput., 15: 287–299, 1986.
24. 24.
J. Matoušek. Linear optimization queries.J. Algorithms, 14:432–448, 1993. Also with O. Schwarzkopf inProc. 8th ACM Symp. on Computational Geometry, pp. 16–25, 1992.
25. 25.
J. Matoušek. On geometric optimization with few violated constraints.Proc. 10th ACM Symp. on Computational Geometry, pp. 312–321, 1994.Google Scholar
26. 26.
J. Matoušek and O. Schwarzkopf. On ray shooting in convex polytopes.Discrete Comput. Geom., 10: 215–232, 1993.
27. 27.
P. McMullen. The maximal number of faces of a convex polytope.Mathematika, 17:179–184, 1970.
28. 28.
N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms.J. Assoc. Comput. Mach., 30:852–865, 1983.
29. 29.
N. Megiddo. Linear programming in linear time when the dimension is fixed.J. Assoc. Comput. Mach., 31:114–127, 1984.
30. 30.
K. Mulmuley. Output sensitive construction of levels and Voronoi diagrams inR dof order 1 tok. Proc. 22nd ACM Symp. on Theory of Computing, pp. 322–330, 1990.Google Scholar
31. 31.
K. Mulmuley,Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, NJ, 1994.Google Scholar
32. 32.
T. Ottmann, S. Schuierer, and S. Soundaralakshmi. Enumerating extreme points in higher dimensions.Proc. 12th Symp. on Theoretical Aspects of Computer Science, pp. 562–570. Lecture Notes in Computer Science, vol. 900. Springer-Verlag, Berlin, 1995.Google Scholar
33. 33.
J. O'Rourke.Computational Geometry in C. Cambridge University Press, Cambridge, 1994.
34. 34.
M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane.J. Comput. System Sci., 23:166–204, 1981.
35. 35.
F. P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions.Commun. ACM, 20:87–93, 1977.
36. 36.
F. P. Preparata and M. I. Shamos.Computational Geometry: An Introduction. Springer-Verlag, New York, 1985.Google Scholar
37. 37.
H. Raynaud. Sur l'enveloppe convexe des nuages des point aléatoires dansR.n.J. Appl. Probab., 7: 35–48, 1970.
38. 38.
M. Reichling. On the detection of a common intersection ofk convex objects in the plane.Inform. Process. Lett., 29:25–29, 1988.
39. 39.
M. Reichling. On the detection of a common intersection ofk convex polyhedra. In H. Noltemeier (ed.),Computational Geometry and Its Applications, pp. 180–186. Lecture Notes in Computer Science, vol. 333. Springer-Verlag, Berlin, 1988.Google Scholar
40. 40.
T. Roos and P. Widmayer.k-Violation linear programming.Inform. Process. Lett., 52:109–114, 1994.
41. 41.
R. Seidel. Constructing higher-dimensional convex hulls at logarithmic cost per face.Proc. 18th ACM Symp. on Theory of Computing, pp. 404–413, 1986.Google Scholar
42. 42.
R. Seidel. Small-dimensional linear programming and convex hulls made easy.Discrete Comput. Geom., 6:423–434, 1991.
43. 43.
M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems.Proc. 9th Symp. on Theoretical Aspects of Computer Science, pp. 569–579. Lecture Notes in Computer Science, vol. 577. Springer-Verlag, Berlin, 1992.Google Scholar
44. 44.
G. F. Swart. Finding the convex hull facet by facet.J. Algorithms, 6:17–48, 1985.
45. 45.
E. Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer (ed.),New Results and New Trends in Computer Science, pp. 359–370, Lecture Notes in Computer Science., vol. 555, Springer-Verlag, Berlin, 1991.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9754315614700317, "perplexity": 10741.69099107108}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-47/segments/1542039746110.52/warc/CC-MAIN-20181119192035-20181119214035-00366.warc.gz"}