Abstract
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three in-place algorithms for computing the convex hull of a planar point set. All three algorithms are optimal, some more so than others. . .
This research was partly funded by the National Science Foundation, the Natural Sciences and Engineering Research Council of Canada and the Danish Natural Science Research Council under contract 9801749 (project Performance Engineering).
Previously a wrong PDF was attached to the online version of this chapter. This has now been corrected.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9:216–219, 1979. Corrigendum, Information Processing Letters, 10:168, 1980.
B. K. Bhattacharya and S. Sen. On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm. Journal of Algorithms, 25(1):177–193, 1997.
T. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16:361–368, 1996.
T. Chan, J. Snoeyink, and C. K. Yap. Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and threedimensional Voronoi diagrams. Discrete & Computational Geometry, 18:433–454, 1997.
B. Chazelle and D. P. Dobkin. Intersection of convex objects in 2 and 3 dimensions. Journal of the ACM, 34:1–27, 1987.
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4(1):387–421, 1988.
E.W. Dijkstra. Smoothsort, an alternative for sorting in situ. Science of Computer Programming, 1(3):223–233, 1982.
E. W. Dijkstra and A. J. M. van Gasteren. An introduction to three algorithms for sorting in situ. Information Processing Letters, 15(3):129–134, 1982.
S. Dvorak and B. Durian. Stable linear time sublinear space merging. The Computer Journal, 30(4):372–375, 1987.
S. Dvorak and B. Durian. Unstable linear time O(1) space merging. The Computer Journal, 31(3):279–282, 1988.
W. Eddy. A new convex hull algorithm for planar sets. ACM Transactions on Mathematical Software, 3(4):398–403, 1977.
R. W. Floyd. Algorithm 245, Treesort 3. Communications of the ACM, 7:401, 1964.
R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132–133, 1972.
E. Horowitz, S. Sahni, and S. Rajasekaran. Computer Algorithms. Computer Science Press, 1998.
B.-C. Huang and M. A. Langston. Practical in-place merging. Communications of the ACM, 31(3):348–352, 1988.
B.-C. Huang and M. A. Langston. Fast stable merging and sorting in constant extrasp ace. The Computer Journal, 35(6):643–650, 1992.
A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2:18–21, 1973.
J. Katajainen, T. Pasanen, and J. Teuhola. Practical in-place mergesort. Nordic Journal of Computing, 3:27–40, 1996.
J. Katajainen and T. A. Pasanen. Stable minimum space partitioning in linear time. BIT, 32(4):580–585, 1992.
J. Katajainen and T. A. Pasanen. In-place sorting with fewer moves. Information Processing Letters, 70(1):31–37, 1999.
D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(1):287–299, 1986.
T. W. Lai and D. Wood. Implicit selection. In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory, volume 318 of Lecture Notes in Computer Science, pages 14–23. Springer-Verlag, 1988.
H. Mannila and E. Ukkonen. A simple linear-time algorithm for in situ merging. Information Processing Letters, 18(4):203–208, 1984.
N. Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114–127, 1984.
P. Morin. insitu.tgz. Available online at http://cgm.cs.mcgill.ca/~morin/, 2001.
J. I. Munro, V. Raman, and J. S. Salowe. Stable in situ sorting and minimum data movement. BIT, 30(2):220–234, 1990.
F. P. Preparata. An optimal real time algorithm for planar convex hulls. Communications of the ACM, 22:402–405, 1979.
F. P. Preparata and S. J. Hong. Convex hulls of finite point sets in two and three dimensions. Communications of the ACM, 2(20):87–93, 1977.
F. P. Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag, 1985.
J. Salowe and W. Steiger. Simplified stable merging tasks. Journal of Algorithms, 8(4):557–571, 1987.
R. Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6:423–434, 1991.
M. I. Shamos. Computational Geometry. PhD thesis, Yale University, 1978.
H. W. Six and L. Wegner. Sorting a random access file in situ. The Computer Journal, 27(3):270–275, 1984.
A. Symvonis. Optimal stable merging. The Computer Journal, 38(8):681–690, 1995.
R. Wenger. Randomized quick hull.Algorithmica, 17:322–329, 1997.
J. W. J. Williams. Algorithm 232, Heapsort. Communications of the ACM, 7:347–348, 1964.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brönnimann, H., Iacono, J., Katajainen, J., Morin, P., Morrison, J., Toussaint, G. (2002). In-Place Planar Convex Hull Algorithms. In: Rajsbaum, S. (eds) LATIN 2002: Theoretical Informatics. LATIN 2002. Lecture Notes in Computer Science, vol 2286. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45995-2_43
Download citation
DOI: https://doi.org/10.1007/3-540-45995-2_43
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43400-9
Online ISBN: 978-3-540-45995-8
eBook Packages: Springer Book Archive