caa a22 4500 469074957 CHVBK 20180323132932.0 cr unu---uuuuu 170328e19920901xx s 000 0 eng 10.1007/BF02293049 doi (NATIONALLICENCE)springer-10.1007/BF02293049 Transitions in geometric minimum spanning trees [Elektronische Daten] [Clyde Monma, Subhash Suri] We study some combinatorial and algorithmic problems associated with an arbitrary motion of input points in space. The motivation for such an investigation comes from two different sources:computer modeling andsensitivity analysis. In modeling, the dynamics enters the picture since geometric objects often model physical entities whose positions can change over time. In sensitivity analysis, the motion of the input points might represent uncertainties in the precise location of objects. The main results of the paper deal with state transitions in the minimum spanning tree when one or more of the input points move arbitrarily in space. In particular, questions of the following form are addressed: (i) How many different minimum spanning trees can arise if one point moves while the others remain fixed? (ii) When does the minimum spanning tree change its topology if all points are allowed to move arbitrarily? Springer-Verlag New York Inc., 1992 Monma Clyde Bell Communications Research, 445 South Street, 07960, Morristown, NJ, USA aut Suri Subhash Bell Communications Research, 445 South Street, 07960, Morristown, NJ, USA aut Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 265-293 0179-5376 8:3<265 1992 8 454 https://doi.org/10.1007/BF02293049 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293049 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Monma Clyde Bell Communications Research, 445 South Street, 07960, Morristown, NJ, USA aut NATIONALLICENCE 700 1- Suri Subhash Bell Communications Research, 445 South Street, 07960, Morristown, NJ, USA aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/3(1992-09-01), 265-293 0179-5376 8:3<265 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer