Computational topology for approximations of knots

Ji Li; T. J. Peters; K. E. Jordan

doi:10.4995/agt.2014.2281

Authors

Ji Li University of Connecticut
T. J. Peters University of Connecticut
K. E. Jordan Cambridge Research Center

DOI:

https://doi.org/10.4995/agt.2014.2281

Keywords:

Knot approximation, ambient isotopy, Bézier curve, subdivision, piecewise linear approximation

Abstract

The preservation of ambient isotopic equivalence under piecewise linear (PL) approximation for smooth knots are prominent in molecular modeling and simulation. Sufficient conditions are given regarding:

Hausdorff distance, and
a sum of total curvature and derivative.

High degree Bézier curves are often used as smooth representations, where computational efficiency is a practical concern. Subdivision can produce PL approximations for a given B\'ezier curve, fulfilling the above two conditions. The primary contributions are:

(i) a priori bounds on the number of subdivision iterations sufficient to achieve a PL approximation that is ambient isotopic to the original B\'ezier curve, and

(ii) improved iteration bounds over those previously established.

Downloads

Download data is not yet available.

Author Biographies

Ji Li, University of Connecticut

Department of Mathematics

T. J. Peters, University of Connecticut

Department of Computer Science and Engineering

K. E. Jordan, Cambridge Research Center

IBM T.J. Watson Research

References

N. Amenta, T. J. Peters and A. C. Russell, Computational topology: Ambient isotopic approximation of 2-manifolds, Theoretical Computer Science 305 (2003), 3-15. https://doi.org/10.1016/S0304-3975(02)00691-6

L. E. Andersson, S. M. Dorney, T. J. Peters and N. F. Stewart, Polyhedral perturbations that preserve topological form, CAGD 12, no. 8 (1995), 785-799. https://doi.org/10.1016/0167-8396(94)00039-7

M. Burr, S. W. Choi, B. Galehouse and C. K. Yap, Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves, Journal of Symbolic Computation 47 (2012), 131-152. https://doi.org/10.1016/j.jsc.2011.08.021

F. Chazal and D. Cohen-Steiner, A condition for isotopic approximation, Graphical Models 67, no. 5 (2005), 390-404. https://doi.org/10.1016/j.gmod.2005.01.005

W. Cho, T. Maekawa and N. M. Patrikalakis, Topologically reliable approximation in terms of homeomorphism of composite Bézier curves, CAGD 13 (1996), 497-520. https://doi.org/10.1016/0167-8396(95)00042-9

E. Denne and J. M. Sullivan, Convergence and isotopy type for graphs of finite total curvature, In: A. I. Bobenko, J. M. Sullivan, P. Schröder, and G. M. Ziegler, editors, Discrete Differential Geometry, pages 163-174. Birkhäuser Basel, 2008. https://doi.org/10.1007/978-3-7643-8621-4_8

G. E. Farin, Curves and surfaces for computer-aided geometric design: A practical code, Academic Press, Inc., 1996.

M. W. Hirsch, Differential topology, Springer, New York, 1976. https://doi.org/10.1007/978-1-4684-9449-5

K. E. Jordan, L. E. Miller, T. J. Peters and A. C. Russell, Geometric topology and visualizing 1-manifolds, In: V. Pascucci, X. Tricoche, H. Hagen, and J. Tierny, editors, Topological Methods in Data Analysis and Visualization, pages 1-13. Springer NY, 2011.

J. Li, Topological and isotopic equivalence with applications to visualization, PhD thesis, University of Connecticut, U.S., 2013.

J. Li and T. J. Peters, Isotopic convergence theorem, Journal of Knot Theory and Its Ramifications 22, no. 3 (2013). https://doi.org/10.1142/S0218216513500120

J. Li, T. J. Peters, D. Marsh and K. E. Jordan, Computational topology counterexamples with 3D visualization of Bézier curves, Applied General Topology 13, no. 2 (2012), 115-134. https://doi.org/10.4995/agt.2012.1624

J. Li, T. J. Peters and J. A. Roulier, Isotopy from Bézier curve subdivision, preprint.

L. Lin and C. Yap, Adaptive isotopic approximation of nonsingular curves: the parameterizability and nonlocal isotopy approach, Discrete & Computational Geometry 45 no. 4 (2011), 760-795. https://doi.org/10.1007/s00454-011-9345-9

T. Maekawa, N. M. Patrikalakis, T. Sakkalis and G. Yu, Analysis and applications of pipe surfaces, CAGD 15, no. 5 (1998), 437-458. https://doi.org/10.1016/S0167-8396(97)00042-3

D. D. Marsh and T. J. Peters, Knot and Bézier curve visualizing tool.

(http://www.cse.uconn.edu/ tpeters/top-viz.html)

L. E. Miller, Discrepancy and Isotopy for Manifold Approximations, PhD thesis, University of Connecticut, U.S., 2009.

J. W. Milnor, On the total curvature of knots, Annals of Mathematics 52 (1950), 248-257. https://doi.org/10.2307/1969467

G. Monge, Application de l'analyse à la géométrie, Bachelier, Paris, 1850.

E. L. F. Moore, T. J. Peters and J. A. Roulier, Preserving computational topology by subdivision of quadratic and cubic Bézier curves, Computing 79, no. 2-4 (2007), 317-323. https://doi.org/10.1007/s00607-006-0208-9

G. Morin and R. Goldman, On the smooth convergence of subdivision and degree elevation for Bézier curves, CAGD 18 (2001), 657-666. https://doi.org/10.1016/S0167-8396(01)00059-0

J. Munkres, Topology, Prentice Hall, 2nd edition, 1999.

D. Nairn, J. Peters and D. Lutterkort, Sharp, quantitative bounds on the distance between a polynomial piece and its Bézier control polygon, CAGD 16 (1999), 613-63. https://doi.org/10.1016/S0167-8396(99)00026-6

M. Reid and B. Szendroi, Geometry and Topology, Cambridge University Press, 2005. https://doi.org/10.1017/CBO9780511807510