×

\((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity. (English) Zbl 1417.68222

Summary: Given a set \(S\) in \(\mathbb {R}^n\), a \((\delta ,\varepsilon)\)-ball approximation of \(S\) is defined as a collection of balls that covers the morphological erosion of \(S\) (by a ball of radius \(\varepsilon\)) and remains inside the morphological dilation of \(S\) (by a ball of radius \(\delta \)). We study the problem of computing a \((\delta ,\varepsilon)\)-ball approximation when \(S\) is itself defined as a finite union of balls. This problem relates to geometric set cover problems but is however different in nature. It offers a new framework for reducing the size of a collection of balls while controlling both the inner and outer distance to the shape. We prove that computing a \((\delta ,\varepsilon)\)-ball approximation of minimum cardinality is NP-complete for \(n = 2\). Along the way, we study the boundary of unions of disks and their erosion, for which we derive a computational description.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Agarwal, P.K., Pan, J.: Near-linear algorithms for geometric hitting sets and set covers. In: Proceedings of the 30th Annual Symposium on Computational Geometry (SOCG’14), pp. 271-279. ACM, New York (2014) · Zbl 1398.68656
[2] Amenta, N., Kolluri, R.K.: Accurate and efficient unions of balls. In: Proceedings of the 16th Annual Symposium on Computational Geometry (SCG’00), pp. 119-128. ACM, New York (2000) · Zbl 1375.68119
[3] Attali, D.; Boissonnat, J-D; Edelsbrunner, H.; Möller, T. (ed.); Hamann, B. (ed.); Russell, RD (ed.), Stability and computation of medial axes: a state-of-the-art report, 109-125 (2009), Berlin · Zbl 1192.68555 · doi:10.1007/b106657_6
[4] Berberich, E.; Eigenwillig, A.; Hemmer, M.; Hert, S.; Mehlhorn, K.; Schömer, E.; Möhring, R. (ed.); Raman, R. (ed.), A computational basis for conic arcs and boolean operations on conic polygons, No. 2461, 174-186 (2002), Berlin · Zbl 1019.68601 · doi:10.1007/3-540-45749-6_19
[5] Bradshaw, G., O’Sullivan, C.: Adaptive medial-axis approximation for sphere-tree construction. ACM Trans. Graph (TOG) 23(1), 1-26 (2004) · doi:10.1145/966131.966132
[6] Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463-479 (1995) · Zbl 0841.68122 · doi:10.1007/BF02570718
[7] Broutta, A.; Coeurjolly, D.; Sivignon, I.; Wiederhold, P. (ed.); Barneva, RP (ed.), Hierarchical discrete medial axis for sphere-tree construction, No. 5852, 56-67 (2009), Berlin · Zbl 1267.68281 · doi:10.1007/978-3-642-10210-3_5
[8] Cabello, S., De Berg, M., Giannopoulos, P., Knauer, C., Van Oostrum, R., Veltkamp, R.C.: Maximizing the area of overlap of two unions of disks under rigid motion. Int. J. Comput. Geom. Appl. 19(6), 533-556 (2009) · Zbl 1194.65035 · doi:10.1142/S0218195909003118
[9] Calamoneri, T.; Petreschi, R.; Du, D-Z (ed.); Li, M. (ed.), An efficient orthogonal grid drawing algorithm for cubic graphs, No. 959, 31-40 (1995), Berlin · doi:10.1007/BFb0030817
[10] Cazals, F., Dreyfus, T., Sachdeva, S., Shah, N.: Greedy geometric algorithms for collection of balls, with applications to geometric spproximation and molecular coarse-graining. Comput. Graph. Forum 33(6), 1-17 (2014) · doi:10.1111/cgf.12270
[11] Chaussard, J., Couprie, M., Talbot, H.: Robust skeletonization using the discrete \[\lambda\] λ-medial axis. Pattern Recognit. Lett. 32(9), 1384-1394 (2011) · doi:10.1016/j.patrec.2010.09.002
[12] Chazal, F., Lieutier, A.: The \[\lambda\] λ-medial axis. Graph. Models 67(4), 304-331 (2005) · Zbl 1175.68487 · doi:10.1016/j.gmod.2005.01.002
[13] Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233-235 (1979) · Zbl 0443.90066 · doi:10.1287/moor.4.3.233
[14] Coeurjolly, D., Montanvert, A.: Optimal separable algorithms to compute the reverse Euclidean distance transformation and discrete medial axis in arbitrary dimension. IEEE Trans. Pattern Anal. Mach. Intell. 29(3), 437-448 (2007) · doi:10.1109/TPAMI.2007.54
[15] Culver, T., Keyser, J., Manocha, D.: Accurate computation of the medial axis of a polyhedron. In: Proceedings of the 5th ACM Symposium on Solid Modeling and Applications (SMA’99), pp. 179-190. ACM, New York (1999) · Zbl 1069.65548
[16] de Rezende, P.J., Miyazawa, F.K., Sasaki, A.T.: A PTAS for the disk cover problem of geometric objects. Oper. Res. Lett. 41(5), 552-555 (2013) · Zbl 1286.68472 · doi:10.1016/j.orl.2013.06.014
[17] Dey, T.K., Zhao, W.: Approximate medial axis as a Voronoi subcomplex. Comput. Aid. Des. 36(2), 195-202 (2004) · doi:10.1016/S0010-4485(03)00061-7
[18] Edelsbrunner, H.; Koehl, P.; Goodman, JE (ed.); Pach, J. (ed.); Welzl, E. (ed.), The geometry of biomolecular solvation, No. 52, 243-275 (2005), Cambridge
[19] Federer, H.: Curvature measures. Trans. Am. Math. Soc. 93, 418-491 (1959) · Zbl 0089.38402 · doi:10.1090/S0002-9947-1959-0110078-1
[20] Feinauer, J., Spettl, A., Manke, I., Strege, S., Kwade, A., Pott, A., Schmidt, V.: Structural characterization of particle systems using spherical harmonics. Mater. Charact. 106, 123-133 (2015) · doi:10.1016/j.matchar.2015.05.023
[21] Fejes Tóth, G.; Goodman, JE (ed.); O’Rourke, J. (ed.), Packing and covering (2004), Boca Raton
[22] Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826-834 (1977) · Zbl 0396.05009 · doi:10.1137/0132071
[23] Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011) · Zbl 1230.68215
[24] Hatcher, A.: Algebr. Topol. Cambridge University Press, Cambridge (2002)
[25] Hubbard, P.M.: Collision detection for interactive graphics applications. IEEE Trans. Vis. Comput. Graph. 1(3), 218-230 (1995) · doi:10.1109/2945.466717
[26] Hubbard, P.M.: Approximating polyhedra with spheres for time-critical collision detection. ACM Trans. Graph. (TOG) 15(3), 179-210 (1996) · doi:10.1145/231731.231732
[27] Johnson, D.S.: Approximation algorithms for combinatorial problems. Comput. Syst. Sci. 9(3), 256-278 (1974) · Zbl 0296.65036 · doi:10.1016/S0022-0000(74)80044-9
[28] Kershner, R.: The number of circles covering a set. Am. J. Math. 61, 665-671 (1939) · JFM 65.0197.03 · doi:10.2307/2371320
[29] Miklos, B., Giesen, J., Pauly, M.: Discrete scale axis representations for 3D geometry. ACM Trans. Graph. (TOG) 29(4), 101 (2010) · doi:10.1145/1778765.1778838
[30] Nguyen, T.-B., Sivignon, I.: Epsilon-covering: a greedy optimal algorithm for simple shapes. In: Canadian Conference on Computational Geometry, Vancouver, pp. 187-194 (2016)
[31] Pach, J. (ed.): New Trends in Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 10. Springer, Berlin (2012) · Zbl 0773.00009
[32] Ranjan, V., Fournier, A.: Matching and interpolation of shapes using unions of circles. Comput. Graph. Forum 15(3), 129-142 (1996) · doi:10.1111/1467-8659.1530129
[33] Serra, J.: Image Analysis and Mathematical Morphology, vol. 1. Academic Press, New York (1982) · Zbl 0565.92001
[34] Wein, R., Zukerman, B.: Exact and efficient construction of planar arrangements of circular arcs and line segments with applications. Tech. Rep. ACS-TR-121200-01. Tel Aviv University (2006)
[35] Wein, R., Berberich, E., Fogel, E., Halperin, D., Hemmer, M., Salzman, O., Zukerman, B.: 2D Arrangements. CGAL: Computational Geometry Algorithms Library
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.