Vi utökar ett träd T med en genväg pq för att minimera det största avståndet mellan två punkter längs den resulterande augmented träd T + pq. Vi studerar detta problem i en kontinuerlig och geometrisk inställning där T är ett geometriskt träd i Euclidean planet, där en genväg är en linje segment som förbinder två punkter längs kanterna på T, och vi anser alla punkter på T + pq (dvs, hörn och punkter längs kanter) när man bestämmer det största avståndet längs T + pq. Vi hänvisar till det största avståndet mellan två punkter längs kanterna som den kontinuerliga diametern för att skilja den från den diskreta diametern, dvs. det största avståndet mellan två hörn. Vi fastställer att en enda genväg är tillräcklig för att minska den kontinuerliga diametern på ett geometriskt träd T om och endast om skärningspunkten mellan alla diametriala vägar av T varken är ett linjesegment eller en enda punkt. Vi bestämmer en optimal genväg för ett geometriskt träd med n raka kanter i O(n log n) tid. Bortsett från löptiden sträcker sig våra resultat till geometriska träd vars kanter är rektifierbara kurvor. Algoritmen för träd generaliserar vår algoritm för stigar.  ACM Subject Classification Ett nätverk är en ansluten, oriktad graf med positiva kantvikter. Ett geometriskt nätverk är ett nätverk som är inbäddat i Euclidean planet vars kanter är rektifierbara kurvor viktade med sin längd. Vi beskriver våra resultat för raka kanter, även om de sträcker sig till mer allmänna kanter. Vi säger att en punkt p ligger på ett geometriskt nätverk G och skriva p  på G när det finns en kant e av G sådan att p är en punkt längs inbäddningen av e. En punkt p på en kant e av längd l delar e i två delkanter av längder (1 − λ) · l och λ · l för något värde λ  och [0, 1]. Vi representerar punkterna om G när det gäller deras relativa position (uttryckt med λ) längs deras innehållande kant, och på så sätt undviker vi tvetydighet vid korsningar.
För ett geometriskt träd T av n hörn inbäddade i Euclidean planet, De Carufel et al. REF gav en O(n log n) tid algoritm för att lägga till en ny kant till T för att minimera den kontinuerliga diametern.
Minimizing the Continuous Diameter When Augmenting a Tree with a Shortcut
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}