RECONFIGURATION OF NON-CROSSING SPANNING TREES

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10491483" target="_blank" >RIV/00216208:11320/24:10491483 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=2hwut~J5-4" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=2hwut~J5-4</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.20382/jocg.v15i1a9" target="_blank" >10.20382/jocg.v15i1a9</a>

Result language

angličtina

Original language name

RECONFIGURATION OF NON-CROSSING SPANNING TREES

Original language description

For a set P of n points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pair of points and no two edges intersect except at a common endpoint. We study the problem of reconfiguring one non-crossing spanning tree of P to another using a sequence of flips where each flip removes one edge and adds one new edge so that the result is again a non-crossing spanning tree of P. There is a known upper bound that 2n-4 flips suffice [Avis and Fukuda, 1996] and a lower bound that 1.5n-5 flips are sometimes necessary. We give improved bounds that depend on how similar the two trees are. Let d be the number of edges in the final tree but not the initial tree, so at least d flips are required. For points in convex position, we prove an upper bound of 2 d- Q(log d) flips. For general point sets we give a reconfiguration algorithm that uses at most 2 n- 4 flips but reduces that to d + n/2- 1 &lt;= 1.5n- 2 flips when one tree is a path and either the points are in convex position or the path is monotone in some direction. We also examine whether the happy edges (those common to the initial and final trees) need to flip, and we use exhaustive search to find exact minimum flip distances for small point sets.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Computational Geometry

ISSN

1920-180X

e-ISSN

1920-180X

Volume of the periodical

15

Issue of the periodical within the volume

1

Country of publishing house

CA - CANADA

Number of pages

30

Pages from-to

224-253

UT code for WoS article

001380579300003

EID of the result in the Scopus database

2-s2.0-85217828372