Aurenhammer, Franz; Jüttler, Bert On computing the convex hull of (piecewise) curved objects. (English) Zbl 1271.68230 Math. Comput. Sci. 6, No. 3, 261-266 (2012). Summary: We utilize support functions to transform the problem of constructing the convex hull of a finite set of curved objects into the problem of computing the upper envelope of piecewise linear functions. This approach is particularly suited if the objects are (possibly intersecting) circular arcs in the plane. Cited in 3 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 65D18 Numerical aspects of computer graphics, image analysis, and computational geometry Keywords:convex hull; support function; circular arcs × Cite Format Result Cite Review PDF Full Text: DOI References: [1] Aichholzer O., Alt H., Rote G.: Matching shapes with a reference point. Int. J. Comput. Geom. Appl. 7, 349–363 (1997) · Zbl 0883.68118 · doi:10.1142/S0218195997000211 [2] Aichholzer O., Aurenhammer F., Hackl T., Jüttler B., Oberneder M., Šír Z.: Computational and structural advantages of circular boundary representation. Int. J. Computat.Geom. Appl. 21, 47–69 (2011) · Zbl 1233.65014 · doi:10.1142/S0218195911003548 [3] Alt H., Cheong O., Vigneron A.: The Voronoi diagram of curved objects. Discret. Comput. Geom. 34, 439–453 (2005) · Zbl 1079.52014 · doi:10.1007/s00454-005-1192-0 [4] Aurenhammer F.: Power diagrams: properties, algorithms, and applications. SIAM J. Comput. 16, 78–96 (1987) · Zbl 0616.52007 · doi:10.1137/0216006 [5] Bajaj C.L., Kim M.-S.: Convex hulls of objects bounded by algebraic curves. Algorithmica 6, 533–553 (1991) · Zbl 0726.68073 · doi:10.1007/BF01759058 [6] Boissonnat J.-D., Cerezo A., Devillers O., Duquesne J., Yvinec M.: An algorithm for constructing the convex hull of a set of spheres in dimension d. Comput. Geom. Theory Appl. 6, 123–130 (1996) · Zbl 0849.68125 · doi:10.1016/0925-7721(95)00024-0 [7] Boissonnat, J.-D., Delage, C.: Convex hull and Voronoi diagram of additively weighted points. In: Proceedings 13th European Symposium on Algorithms, vol. 3669, pp. 367–378, Springer LNCS (2005) · Zbl 1162.68736 [8] Boissonnat, J.-D., Karavelas, M.: On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres. In: Proceedings 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 305–312, (2003) · Zbl 1094.68676 [9] Dobkin D.P., Souvaine D.L.: Computational geometry in a curved world. Algorithmica 5, 421–457 (1990) · Zbl 0696.68101 · doi:10.1007/BF01840397 [10] Ghosh P.K., Kumar K.V.: Support function representation of convex bodies, its application in geometric computing, and some related representations. Comput. Vision Image Underst. 72, 397–403 (1998) [11] Graham R.: An efficient algorithm for determining the convex hull of a finite point set. Inf. Process. Lett. 1, 132–133 (1972) · Zbl 0236.68013 · doi:10.1016/0020-0190(72)90045-2 [12] Gruber P.M., Wills J.M.: Handbook of Convex Geometry. Elsevier, North-Holland, Amsterdam (1993) · Zbl 0777.52001 [13] Jarvis R.A.: On the identification of the convex hull of a finite set of points in the plane. Inf. Process. Lett. 2, 18–21 (1973) · Zbl 0256.68041 · doi:10.1016/0020-0190(73)90020-3 [14] Kirkpatrick D.G., Seidel R.: The ultimate planar convex hull algorithm?. SIAM J. Comput. 15, 287–299 (1986) · Zbl 0589.68035 · doi:10.1137/0215021 [15] Li Z., Meek D.S.: Smoothing an arc spline. Comput. Graph. 29, 576–587 (2005) · doi:10.1016/j.cag.2005.05.009 [16] Melkman A.: On-line construction of the convex hull of a simple polygon. Inf. Process. Lett. 25, 11–12 (1987) · Zbl 0653.68028 · doi:10.1016/0020-0190(87)90086-X [17] Nielsen F., Yvinec M.: An output-sensitive convex hull algorithm for planar objects. Int. J. Comput. Geom. Appl. 8, 39–65 (1998) · Zbl 0957.68118 · doi:10.1142/S0218195998000047 [18] Piegl L.A., Tiller W.: Biarc approximation of NURBS curves. Comput. Aided Des. 34, 807–814 (2002) · doi:10.1016/S0010-4485(01)00160-9 [19] Prince J.R., Willsky A.S.: Reconstructing convex sets from support line measurements. IEEE Trans. Pattern Anal. Mach. Intell. 12, 377–389 (1990) · doi:10.1109/34.50623 [20] Rappaport D.: A convex hull algorithm for discs, and applications. Comput. Geom. Theory Appl. 1, 171–187 (1992) · Zbl 0772.68108 · doi:10.1016/0925-7721(92)90015-K [21] Richardson T.J.: Approximation of planar convex sets from hyperplanes probes. Discret. Comput. Geom. 18, 151–177 (1997) · Zbl 0939.52001 · doi:10.1007/PL00009313 [22] Schäffer A.A., Van Wyk C.J.: Convex hulls of piecewise-smooth Jordan curves. J. Algorithms 8, 66–94 (1987) · Zbl 0642.68082 · doi:10.1016/0196-6774(87)90028-9 [23] Sharir M., Agarwal P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995) · Zbl 0834.68113 [24] Yue Y., Murray J.L., Corney J.R., Clark D.E.R.: Convex hull of a planar set of straight and circular line segments. Eng. Comput. 16, 858–875 (1999) · Zbl 0962.65016 · doi:10.1108/02644409910304086 [25] Yap C.K.: An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments. Discret. Comput. Geom. 2, 365–393 (1987) · Zbl 0628.68042 · doi:10.1007/BF02187890 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.