×
Farouki, Rida T.; Han, Chang Yong; Hass, Joel

Boundary evaluation algorithms for Minkowski combinations of complex sets using topological analysis of implicit curves. (English) Zbl 1087.65011

Numer. Algorithms 40, No. 3, 251-283 (2005).
The Minkowski geometric algebra of complex sets is concerned with sets of complex numbers generated by algebraic combinations of complex values that vary independently over prescribed complex-set operands. This algebra provides an extension of real interval arithmetic to sets of complex numbers, and has applications in computer graphics and image analysis, geometrical optics, and dynamical stability analysis.
The focus in this paper is on geometrically-motivated new insights and algorithms for the efficient computation of Minkowski sums, products, swept volumes, and Horner terms. Available algorithms to compute the boundaries of Minkowski sums and products invoke a dissection of the parametrized set boundaries into segment pairs, along which certain matching criteria hold. Taking the sum or product of corresponding points along each segment pair yields an unorganized set of candidate edges for the Minkowski sum or product boundary. The true boundary is obtained through a time-consuming process of culling edges that lie in the interior of the set, and organizing the remaining edges in proper order.
In this paper, the authors present a new approach, whereby the matching condition is regarded as an implicit curve in the space \({\mathbb R}^n\) whose coordinates are boundary parameters for the \(n\) given sets.
The analysis of the topological configuration of this curve facilitates the identification of sets of segments on the operand boundaries that generate boundary segments of the Minkowski set, and the rejection of certain sets that satisfy the matching criterion but yield only interior edges.
Geometrical relations between the operand set boundaries and the implicit curve in \({\mathbb R}^n\) are derived, and the use of the method in the context of Minkowski sums, products, planar swept volumes, and Horner terms is described.
Reviewer: Sonia Pérez Díaz (Madrid)

Cited in 3 Documents

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
65G30 Interval and finite arithmetic
51B20 Minkowski geometries in nonlinear incidence geometry

Keywords:

Minkowski geometric algebra; Minkowski sums and products; planar swept volumes; Horner terms; boundary evaluation; implicit curves; curve description algorithm; topological configuration; matching condition; interval arithmetic; algorithms
Cite Review PDF
Full Text: DOI

References:

[1] S. Arnborg and H. Feng, Algebraic decomposition of regular curves, J. Symbolic Comput. 5 (1988) 131–140. · Zbl 0666.14012 · doi:10.1016/S0747-7171(88)80009-9
[2] D.S. Arnon, Topologically reliable display of algebraic curves, ACM Computer Graphics 17 (1983) 219–227. · doi:10.1145/964967.801152
[3] D.S. Arnon, G.E. Collins and S. McCallum, Cylindrical algebraic decomposition I: The basic algorithm, SIAM J. Computing 13 (1984) 865–877. · Zbl 0562.14001 · doi:10.1137/0213054
[4] D.S. Arnon, G.E. Collins and S. McCallum, Cylindrical algebraic decomposition II: An adjacency algorithm for the plane, SIAM J. Computing 13 (1984) 878–889. · Zbl 0562.14001 · doi:10.1137/0213055
[5] D.S. Arnon and S. McCallum A polynomial-time algorithm for the topological type of a real algebraic curve, J. Symbolic Comput. 5 (1988) 213–236. · Zbl 0664.14017 · doi:10.1016/S0747-7171(88)80013-0
[6] P. Cellini, P. Gianni and C. Traverso, Algorithms for the shape of semialgebraic sets: A new approach, in: Lecture Notes in Computer Science, Vol. 539 (Springer, New York, 1991) pp. 1–18. · Zbl 0779.14022
[7] R.T. Farouki and J.-C.A. Chastang, Curves and surfaces in geometrical optics, in: Mathematical Methods in Computer Aided Geometric Design II, eds. T. Lyche and L.L. Schumaker (Academic Press, New York, 1992) pp. 239–260.
[8] R.T. Farouki and J.-C.A. Chastang, Exact equations of ”simple” wavefronts, Optik 91 (1992) 109–121.
[9] R.T. Farouki, W. Gu and H.P. Moon, Minkowski roots of complex sets, in: Geometric Modeling and Processing 2000 (IEEE Computer Soc. Press, Los Alamitos, CA, 2000) pp. 287–300.
[10] R.T. Farouki and C.Y. Han, Computation of Minkowski values of polynomials over complex sets, Numer. Algorithms 36 (2004) 13–29. · Zbl 1073.12006 · doi:10.1023/B:NUMA.0000027725.80448.d8
[11] R.T. Farouki and C.Y. Han, Solution of elementary equations in the Minkowski geometric algebra of complex sets, Adv. Comput. Math. 22 (2005) 301–323. · Zbl 1065.51002 · doi:10.1007/s10444-003-2605-3
[12] R.T. Farouki and C.Y. Han, Root neighborhoods, generalized lemniscates, and robust stability of dynamic systems, Preprint (2005). · Zbl 1192.65018
[13] R.T. Farouki, C.Y. Han, J. Hass and T.W. Sederberg, Topologically consistent trimmed surface approximations based on triangular patches, Computer Aided Geom. Design 21 (2004) 459–478. · Zbl 1069.65552
[14] R.T. Farouki and H.P. Moon, Minkowski geometric algebra and the stability of characteristic polynomials, in: Visualization in Mathematics, Vol. 3, eds. H.-C. Hege and K. Polthier (Springer, Berlin, 2003) pp. 163–188. · Zbl 1175.93182
[15] R.T. Farouki, H.P. Moon and B. Ravani, Algorithms for Minkowski products and implicitly-defined complex sets, Adv. Comput. Math. 13 (2000) 199–229. · Zbl 0948.65016 · doi:10.1023/A:1018910412112
[16] R.T. Farouki, H.P. Moon and B. Ravani, Minkowski geometric algebra of complex sets, Geometriae Dedicata 85 (2001) 283–315. · Zbl 0987.51012 · doi:10.1023/A:1010318011860
[17] R.T. Farouki and H. Pottmann, Exact Minkowski products of N complex disks, Reliable Computing 8 (2002) 43–66. · Zbl 1028.65048 · doi:10.1023/A:1014737602641
[18] P.K. Ghosh, A mathematical model for shape description using Minkowski operators, Computer Vision Graphics Image Processing 44 (1988) 239–269. · doi:10.1016/0734-189X(88)90123-5
[19] L. Gonzalez-Vega and I. Necula, Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geom. Design 19 (2002) 719–743. · Zbl 1043.68105 · doi:10.1016/S0167-8396(02)00167-X
[20] T.A. Grandine and F.W. Klein, A new approach to the surface intersection problem, Computer Aided Geom. Design 14 (1997) 111–134. · Zbl 0906.68151 · doi:10.1016/S0167-8396(96)00024-6
[21] H. Hadwiger, Vorlesungen über Inhalt, Oberfläche, und Isoperimetrie (Springer, Berlin, 1957). · Zbl 0078.35703
[22] J. Hass, R.T. Farouki, C.Y. Han, X. Song and T.W. Sederberg, Guaranteed consistency of surface intersections and trimmed surfaces using a coupled topology resolution and domain decomposition scheme, Adv. Comput. Math. (2005), to appear. · Zbl 1118.65011
[23] H. Hong, An efficient method for analyzing the topology of plane real algebraic curves, Math. Comput. Simulation 42 (1996) 571–582. · Zbl 1037.14503 · doi:10.1016/S0378-4754(96)00034-1
[24] A. Kaul, Computing Minkowski sums, Ph.D. thesis, Columbia University (1993).
[25] A. Kaul and R.T. Farouki, Computing Minkowski sums of plane curves, Internat. J. Comput. Geometry Appl. 5 (1995) 413–432. · Zbl 0854.68102 · doi:10.1142/S0218195995000258
[26] A. Kaul and J.R. Rossignac, Solid interpolating deformations: Construction and animation of PIP, Comput. Graphics 16 (1992) 107–115. · doi:10.1016/0097-8493(92)90077-9
[27] T. Lozano-Pérez and M.A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Commun. ACM 22 (1979) 560–570. · doi:10.1145/359156.359164
[28] G. Matheron, Random Sets and Integral Geometry (Wiley, New York, 1975). · Zbl 0321.60009
[29] A.E. Middleditch, Applications of a vector sum operator, Computer Aided Design 20 (1988) 183–188. · Zbl 0656.65021 · doi:10.1016/0010-4485(88)90275-8
[30] H. Minkowski, Volumen und Oberfläche, Math. Annalen 57 (1903) 447–495. · JFM 34.0649.01 · doi:10.1007/BF01445180
[31] R.E. Moore, Interval Analysis (Prentice-Hall, Englewood Cliffs, NJ, 1966). · Zbl 0176.13301
[32] R.E. Moore, Methods and Applications of Interval Analysis (SIAM, Philadelphia, PA, 1979). · Zbl 0417.65022
[33] M.-F. Roy and A. Szpirglas, Complexity of the computation of cylindrical decomposition and topology of real algebraic curves using Thom’s lemma, in: Lecture Notes in Mathematics, Vol. 1420 (Springer, New York, 1990) pp. 223–236. · Zbl 0718.14028
[34] T. Sakkalis, The topological configuration of a real algebraic curve, Bull. Austral. Math. Soc. 43 (1991) 37–50. · Zbl 0716.14034 · doi:10.1017/S0004972700028756
[35] J. Serra, Image Analysis and Mathematical Morphology (Academic Press, London, 1982). · Zbl 0565.92001
[36] J. Serra, Introduction to mathematical morphology, Computer Vision Graphics Image Processing 35 (1986) 283–305. · Zbl 0648.92001 · doi:10.1016/0734-189X(86)90002-2
[37] X.W. Song, T.W. Sederberg, J. Zheng, R.T. Farouki and J. Hass, Linear perturbation methods for topologically consistent representations of free-form surface intersections, Computer Aided Geom. Design 21 (2004) 303–319. · Zbl 1069.65567 · doi:10.1016/j.cagd.2003.11.004
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.