zbMATH — the first resource for mathematics

Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. (English) Zbl 1089.65014
Summary: We present space-efficient algorithms for computing the convex hull of a simple polygonal line in-place, in linear time. It turns out that the problem is as hard as in-place stable partition, i.e., if there were a truly simple solution then in-place stable partition would also have a truly simple solution, and vice versa. Nevertheless, we present a simple self-contained solution that uses \(O(\log n)\) space, and indicate how to improve it to O(1) space with the same techniques used for stable partition. If the points inside the convex hull can be discarded, then there is a truly simple solution that uses a single call to stable partition, and even that call can be spared if only extreme points are desired (and not their order). If the polygonal line is closed, the problem admits a very simple solution which does not call for stable partitioning at all.

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
52B55 Computational aspects related to convexity
Full Text: DOI
[1] Aloupis, G., A history of linear-time convex hull algorithms for simple polygons
[2] Boissonnat, J.-D.; Yvinec, M., Algorithmic geometry, (1998), Cambridge University Press Cambridge
[3] Brönnimann, H.; Chen, E.Y.; Chan, T.M., Towards in-place geometric algorithms and data structures, (), 239-246 · Zbl 1374.68646
[4] Brönnimann, H.; Iacono, J.; Katajainen, J.; Morin, P.; Morrison, J.; Toussaint, G.T., Space-efficient planar convex hull algorithms, Theoret. comput. sci., 321, 1, 25-40, (2004) · Zbl 1068.68153
[5] Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C., Introduction to algorithms, (2001), MIT Press Cambridge, MA
[6] Chen, E.Y.; Chan, T.M., A space-efficient algorithm for segment intersection, (), 68-71
[7] Geffert, V.; Katajainen, J.; Pasanen, T., Asymptotically efficient in-place merging, Theoret. comput. sci., 237, 159-181, (2000) · Zbl 0939.68160
[8] Katajainen, J.; Pasanen, T., Stable minimum space partitioning in linear time, Bit, 32, 580-585, (1982) · Zbl 0756.68025
[9] Katajainen, J.; Pasanen, T., Sorting multiset stably in minimum space, Acta informatica, 31, 410-421, (1994)
[10] Katajainen, J.; Pasanen, T.; Teuhola, J., Practical in-place mergesort, Nordic J. comput., 3, 27-40, (1996)
[11] Lee, D.T., On finding the convex hull of a simple polygon, Int. J. computing info. sci., 12, 2, 87-98, (1983) · Zbl 0543.52002
[12] Melkman, A., On-line construction of the convex hull of a simple polygon, Inform. process. lett., 25, 11-12, (1987) · Zbl 0653.68028
[13] Munro, J.I.; Raman, V.; Salowe, J.S., Stable in situ sorting and minimum data movement, Bit, 30, 2, 220-234, (1990) · Zbl 0696.68086
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.