# 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.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 65G40 General methods in interval analysis
Full Text:
##### References:
  G. Birkhoff, Lattice theory, Technical Report XXV, American Mathematical Society Colloquium Publications, Providence, RI, 1940. · Zbl 0063.00402  Davey, B.A.; Priestley, H.A., Introduction to lattices and order, (2002), Cambridge University Press Cambridge · Zbl 1002.06001  Diestel, R., Graph theory (graduate texts in mathematics), Vol. 173, (2000), Springer Berlin  Janich, K., Topology (undergraduate texts in mathematics), (1984), Springer Berlin  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  Karp, R.M.; Tarjan, R.E., Linear expected-time algorithms for connectivity problems (extended abstract), (), 368-377  Lozano-Pérez, T., Spatial planning: a configuration space approach, IEEE trans. comput., 32, 2, 108-120, (1983) · Zbl 0513.68081  Milnor, J.W., Morse theory, (1963), Princeton University Press Princeton  Moore, R.E., Methods and applications of interval analysis, (1979), SIAM Philadelphia, PA · Zbl 0417.65022  Munkres, J.R., Elements of algebraic topology, (1984), Addison-Wesley Reading, MA · Zbl 0673.55001  Stander, B.T.; Hart, J.C., Guaranteeing the topology of an implicit surface polygonization for interactive modeling, (), 279-286  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.