Using interval arithmetic to prove that a set is path-connected

被引：14
作者：
Delanoue, N [1 ]
Jaulin, L [1 ]
Cottenceau, B [1 ]
机构：
[1] ISTIA, Lab Ingn Syst Automatises, F-49000 Angers, France
来源：
THEORETICAL COMPUTER SCIENCE | 2006年 / 351卷 / 01期
关键词：
interval arithmetic; graph theory; connected set; topology; set computation; automatic proof;
D O I：
10.1016/j.tcs.2005.09.055
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we give a numerical algorithm able to prove whether a set 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 S. Examples illustrate the principle of the approach. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：119 / 128
页数：10
相关论文
共 12 条
[1]  
BIRKHOFF G, 1940, AM MATH SOC C PUBL P
[2]  
Davey B. A., 2002, INTRO LATTICES ORDER, DOI DOI 10.1017/CBO9780511809088
[3]  
DIESTEL R, 2000, GRAPH THEORY GRADUAT, V173
[4]  
JANICH K, 1984, TOPOLOGY UNDERGRADUA
[5]  
Jaulin L., 2001, APPL INTERVAL ANAL, DOI DOI 10.1007/978-1-4471-0249-6
[6]  
Karp R.M., 1980, P 12 ANN ACM S THEOR, P368
[7]   SPATIAL PLANNING - A CONFIGURATION SPACE APPROACH [J].
LOZANOPEREZ, T .
IEEE TRANSACTIONS ON COMPUTERS, 1983, 32 (02) :108-120
[8]  
Milnor J., 1963, MORSE THEORY
[9]  
Moore R.E., 1979, STUDIES APPL NUMERIC
[10]  
Munkres J R., 1984, Elements of algebraic topology
12