Tutorials and ReviewsNo Access

MULTIPLE PARAMETER CONTINUATION: COMPUTING IMPLICITLY DEFINED k-MANIFOLDS

MICHAEL E. HENDERSON

IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY 10598, USA

https://doi.org/10.1142/S0218127402004498Cited by:110 (Source: Crossref)

Abstract

We present a new continuation method for computing implicitly defined manifolds. The manifold is represented as a set of overlapping neighborhoods, and extended by an added neighborhood of a boundary point. The boundary point is found using an expression for the boundary in terms of the vertices of a set of finite, convex polyhedra. The resulting algorithm is quite simple, allows adaptive spacing of the computed points, and deals with the problems of local and global overlap in a natural way. The algorithm is robust (the new points need only be near the boundary), and is well suited to problems with large embedding dimension, and small to moderate dimension.

Keywords:

References

A. V. Aho and J. D. Ullman , Foundations of Computer Science ( Computer Science Press , NY , 1992 ) . Google Scholar
E. L. Allgower and K. Georg, SIAM Rev. 22, 28 (1980). Web of Science, Google Scholar
E. L. Allgower and P. H. Schmidt, SIAM J. Numer. Anal. 22(2), 322 (1985). Web of Science, Google Scholar
E. L. Allgower and S. Gnutzmann, SIAM J. Numer. Anal. 24(2), 452 (1987). Web of Science, Google Scholar
D. G. Aronson, E. J. Doedel and H. G. Othmer, Int. J. Bifurcation and Chaos 1(1), 51 (1991). Link, Web of Science, Google Scholar
F. Aurenhammer and H. Edelsbrunner, Patt. Recogn. 17(2), 251 (1984). Web of Science, Google Scholar
F. Aurenhammer, SIAM J. Comput. 16(1), 78 (1987). Web of Science, Google Scholar
F. Aurenhammer, J. Algorith. 9, 151 (1988). Web of Science, Google Scholar
F. Aurenhammer, ACM Comput. Surv. 23(3), 345 (1991). Web of Science, Google Scholar
U. Betke and M. Henk, Discret. Comput. Geom. 19, 197 (1998). Web of Science, Google Scholar
J. Bloomenthal, Comput. Aided Geom. Design 5(4), 341 (1988). Google Scholar
M. L. Brodzik and W. C. Rheinboldt, Comput. Math. Appl. 28(9), 9 (1994). Web of Science, Google Scholar
M. L. Brodzik, Comput. Math. Appl. 36(6), 93 (1998). Web of Science, Google Scholar
W. Brostow, J.-P. Dussault and B. L. Fox, J. Comput. Phys. 29, 81 (1978). Web of Science, Google Scholar
P.-C. Chen, P. Hansen and B. Jaumard, Operat. Res. Lett. 10, 403 (1991). Web of Science, Google Scholar
J. Cohen and T. Hickey, J. ACM 26(3), 401 (1979). Web of Science, Google Scholar
J. H. Conway and N. J. A. Sloan , Sphere Packings, Lattices and Groups , 2nd edn. ( Springer-Verlag , 1993 ) . Google Scholar
D. A. Dobkinet al., ACM Trans. Graph. 9(4), 389 (1990). Web of Science, Google Scholar
E. Doedel, Int. J. Bifurcation and Chaos 7(9), 2127 (1997), DOI: 10.1142/S0218127497001576. Link, Web of Science, Google Scholar
H. Edelsbrunner, Discret. Comput. Geom. 13, 415 (1995). Web of Science, Google Scholar
C. B. Garcia and W. I. Zangwill , Pathways to Solutions, Fixed Points, and Equilibria ( Prentice-Hall , Englewood Cliffs, NJ , 1981 ) . Google Scholar
P. E. Gill , W. Murray and M. H. Wright , Practical Optimization ( Academic Press , NY , 1981 ) . Google Scholar
W. J. F. Govaerts , Numerical Methods for Bifurcations of Dynamical Equilibria ( SIAM , Philadelphia , 2000 ) . Google Scholar
B. Grunbaum , Convex Polytopes ( Interscience Publishers , London , 1967 ) . Google Scholar
M. Hall and J. Warren, IEEE Comput. Graph. Appl. 10(6), 33 (1990). Web of Science, Google Scholar
M. E. Henderson, M. Levi and F. Odeh, Int. J. Bifurcation and Chaos 1(1), 27 (1991). Link, Web of Science, Google Scholar
Henderson, M. E. [1993] "Computing implicitly defined surfaces: Two parameter continuation," Research Report 18777, IBM Research . Google Scholar
H. Imai, M. Iri and K. Murota, SIAM J. Comput. 14(1), 93 (1985). Web of Science, Google Scholar
T. A. Jones , D. E. Hamilton and C. R. Johnson , Contouring Geologic Surfaces with the Computer ( Van Nostrand Rheinhold , 1986 ) . Google Scholar
H. B. Keller, Applications of Bifurcation Theory, ed. P. Rabinowitz (Academic Press, NY, 1977) pp. 359–384. Google Scholar
R. Klein , Concrete and Abstract Voronoi Diagrams , Lecture Notes in Computer Science 400 ( Springer-Verlag , Berlin , 1987 ) . Google Scholar
W. Lorensen and H. Cline, Comput. Graph. 21(4), 163 (1987). Google Scholar
K. Melhorn, S. Meiser and C. Ó'Dúnlaing, On the construction of abstract voronoi diagrams, STACS 90, 7th Ann. Symp. Theoretical Aspects of Computer Science, eds. C. Choffrut and T. Lengauer (Springer-Verlag, 1990) pp. 227–239. Google Scholar
R. Melville and D. S. Mackey, Comput. Math. Appl. 30(1), 31 (1995). Web of Science, Google Scholar
A. Morgan , Solving Polynomial Systems using Continuation for Engineering and Scientific Problems ( Prentice-Hall , Englewood Cliffs, NJ , 1987 ) . Google Scholar
P. Ning and J. Bloomenthal, IEEE Comput. Graph. Appl. 13(6), 33 (1993). Web of Science, Google Scholar
W. C. Rheinboldt, Bifurcation: Analysis, Algorithms, Applications, ISNM79, eds. T. Kupper, R. Seydel and H. Troger (Birkhäuser Verlag, The University of Dortmund, Basel, 1987) pp. 256–267. Google Scholar
W. C. Rheinboldt, Numer. Math. 53(1&2), 165 (1988). Web of Science, Google Scholar
M. A. Sabin , Fundamental Algorithms for Computer Graphics , ed. R. A. Earnshaw ( Springer-Verlag , NY , 1985 ) . Google Scholar
R. Seydel, Int. J. Bifurcation and Chaos 7(9), 2105 (1997), DOI: 10.1142/S0218127497001564. Link, Web of Science, Google Scholar
R. E. Tarjan , Data Structures and Network Algorithms ( Society for Industrial and Applied Mathematics , Philadelphia, PA , 1983 ) . Google Scholar
L. F. Tóth, Discret. Comput. Geom. 22, 161 (1999). Web of Science, Google Scholar
D. F. Watson , Contouring: A Guide to the Analysis and Display of Spatial Data ( Pergamon Press , 1992 ) . Google Scholar
C. Zahlten and H. Jürgens, EUROGRAPHICS '91, eds. F. Post and W. Barth (Elsevier Science Publishers, 1973) pp. 5–19. Google Scholar
D. Zwillinger, Standard Mathematical Tables and Formulae, 30th edn. (CRC Press, 1996). Google Scholar