RECONFIGURATION OF NON-CROSSING SPANNING TREES

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

RECONFIGURATION OF NON-CROSSING SPANNING TREES

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

RECONFIGURATION OF NON-CROSSING SPANNING TREES

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název periodika

Journal of Computational Geometry

ISSN

1920-180X

e-ISSN

1920-180X

Svazek periodika

15

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

CA - Kanada

Počet stran výsledku

30

Strana od-do

224-253

Kód UT WoS článku

001380579300003

EID výsledku v databázi Scopus

2-s2.0-85217828372