zbMATH — the first resource for mathematics

Using interval arithmetic to prove that a set is path-connected. (English) Zbl 1087.68068
Summary: We give a numerical algorithm able to prove whether a set \(\mathbb S\) described by nonlinear inequalities is path-connected or not. To our knowledge, no other algorithm (numerical or symbolic) is able to deal with this type of problem. The proposed approach uses interval arithmetic to build a graph which has exactly the same number of connected components as \(\mathbb S\). Examples illustrate the principle of the approach.

68R10 Graph theory (including graph drawing) in computer science
65G40 General methods in interval analysis
Full Text: DOI
[1] G. Birkhoff, Lattice theory, Technical Report XXV, American Mathematical Society Colloquium Publications, Providence, RI, 1940. · Zbl 0063.00402
[2] Davey, B.A.; Priestley, H.A., Introduction to lattices and order, (2002), Cambridge University Press Cambridge · Zbl 1002.06001
[3] Diestel, R., Graph theory (graduate texts in mathematics), Vol. 173, (2000), Springer Berlin
[4] Janich, K., Topology (undergraduate texts in mathematics), (1984), Springer Berlin
[5] Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E., Applied interval analysis, with examples in parameter and state estimation, robust control and robotics, (2001), Springer London · Zbl 1023.65037
[6] Karp, R.M.; Tarjan, R.E., Linear expected-time algorithms for connectivity problems (extended abstract), (), 368-377
[7] Lozano-Pérez, T., Spatial planning: a configuration space approach, IEEE trans. comput., 32, 2, 108-120, (1983) · Zbl 0513.68081
[8] Milnor, J.W., Morse theory, (1963), Princeton University Press Princeton
[9] Moore, R.E., Methods and applications of interval analysis, (1979), SIAM Philadelphia, PA · Zbl 0417.65022
[10] Munkres, J.R., Elements of algebraic topology, (1984), Addison-Wesley Reading, MA · Zbl 0673.55001
[11] Stander, B.T.; Hart, J.C., Guaranteeing the topology of an implicit surface polygonization for interactive modeling, (), 279-286
[12] Walter, E.; Pronzato, L., Identification of parametric models from experimental data, (1997), Springer Berlin
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.