Abstract
We present a purely numerical (i.e., non-algebraic) subdivision algorithm for computing an isotopic approximation of a simple arrangement of curves. The arrangement is “simple” in the sense that any three curves have no common intersection, any two curves intersect transversally, and each curve is non-singular. A curve is given as the zero set of an analytic function on the plane, along with effective interval forms of the function and its partial derivatives. Our solution generalizes the isotopic curve approximation algorithms of Plantinga-Vegter (2004) and Lin-Yap (2009). We use certified numerical primitives based on interval methods. Such algorithms have many favorable properties: they are practical, easy to implement, suffer no implementation gaps, integrate topological with geometric computation, and have adaptive as well as local complexity. A preliminary implementation is available in Core Library.
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
Boissonnat, J.-D., Cohen-Steiner, D., Mourrain, B., Rote, G., Vegter, G.: Meshing of surfaces. In: Boissonnat, Teillaud (eds.) [2], ch. 5
Boissonnat, J.-D., Teillaud, M. (eds.): Effective Computational Geometry for Curves and Surfaces. Springer (2006)
Burr, M., Choi, S., Galehouse, B., Yap, C.: Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves. In: 33rd Int’l Symp. Symb. and Alge. Comp., pp. 87–94 (2008); Special Issue of JSC 47(2), 131–152 (2012)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Berlin (1997)
Kulpa, W.: The Poincaré-Miranda theorem. The American Mathematical Monthly 104(6), 545–550 (1997)
Lin, L., Yap, C.: Adaptive isotopic approximation of nonsingular curves: the parameterizability and nonlocal isotopy approach. Discrete and Comp. Geom. 45(4), 760–795 (2011)
Moore, R.E.: Interval Analysis. Prentice Hall, Englewood Cliffs (1966)
Moore, R.E., Kioustelidis, J.B.: A simple test for accuracy of approx. solns. to nonlinear (or linear) systems. SIAM J. Numer. Anal. 17(4), 521–529 (1980)
Newman, T.S., Yi, H.: A survey of the marching cubes algorithm. Computers & Graphics 30, 854–879 (2006)
Plantinga, S.: Certified Algorithms for Implicit Surfaces. Ph.D. thesis, Groningen University, Inst. for Math. and Comp. Sc., Groningen, Netherlands (December 2006)
Plantinga, S., Vegter, G.: Isotopic approximation of implicit curves and surfaces. In: Proc. Eurographics SGP, pp. 245–254. ACM Press, New York (2004)
Stahl, V.: Interval Methods for Bounding the Range of Poly. and Solving Systems of Nonlin. Eqns. Ph.D. thesis, Johannes Kepler University, Linz (1995)
Yap, C.K.: Complete subdivision algorithms, I: Intersection of Bezier curves. In: 22nd ACM Symp. on Comp. Geom., pp. 217–226 (July 2006)
Yu, J., Yap, C., Du, Z., Pion, S., Brönnimann, H.: The Design of Core 2: A Library for Exact Numeric Computation in Geometry and Algebra. In: Fukuda, K., van der Hoeven, J., Joswig, M., Takayama, N. (eds.) ICMS 2010. LNCS, vol. 6327, pp. 121–141. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lien, JM., Sharma, V., Vegter, G., Yap, C. (2014). Isotopic Arrangement of Simple Curves: An Exact Numerical Approach Based on Subdivision. In: Hong, H., Yap, C. (eds) Mathematical Software – ICMS 2014. ICMS 2014. Lecture Notes in Computer Science, vol 8592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44199-2_43
Download citation
DOI: https://doi.org/10.1007/978-3-662-44199-2_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44198-5
Online ISBN: 978-3-662-44199-2
eBook Packages: Computer ScienceComputer Science (R0)