Vi försöker öka ett geometriskt nätverk i Euclidean planet med genvägar för att minimera dess kontinuerliga diameter, dvs. det största nätverksavståndet mellan två punkter på det utökade nätverket. Till skillnad från i den diskreta inställningen där en genväg ansluter två hörn och diametern mäts mellan hörn, tar vi alla punkter längs kanterna på nätverket i beaktande när du placerar en genväg och när du mäter avstånd i det utökade nätverket. Vi studerar detta nätverk enhancement problem för vägar och cykler. För vägar bestämmer vi en optimal genväg i linjär tid. För cykler visar vi att en enda genväg aldrig minskar den kontinuerliga diametern och att två genvägar alltid räcker för att minska den kontinuerliga diametern. Dessutom karakteriserar vi optimala par av genvägar för konvexa och icke-konvexa cykler. Slutligen utvecklar vi en linjär tid algoritm som producerar ett optimalt par genvägar för konvexa cykler. Förutom algoritmerna sträcker sig våra resultat till rektifierbara kurvor. Vårt arbete avslöjar några av de underliggande utmaningar som måste övervinnas när man tar itu med den diskreta versionen av detta nätverk augmentation problem, där vi minimerar den diskreta diametern på ett nätverk med genvägar som endast ansluter hörn.  ACM Subject Classification The minimum-diameter network augmentation problem handlar om att minimera det största avståndet mellan två hörn av en kant-viktad graf genom att införa nya kanter som genvägar. Vi studerar detta problem i en kontinuerlig och geometrisk inställning där nätverket är en geometrisk graf inbäddad i Euclidean planet, vikten av en genväg är Euclidean avståndet av dess slutpunkter, och genvägar kan införas mellan två punkter längs nätverket som kan vara hörn eller punkter längs kanter. Som ett urval ansökan, överväga ett nätverk av motorvägar där vi mäter avståndet mellan två platser i termer av restid. En stadsingenjör kanske vill förbättra den värsta restiden längs en motorväg eller längs en ringväg genom att införa genvägar. Vårt arbete ger råd om var dessa genvägar ska byggas. Till exempel visar vi var * Detta arbete stöddes delvis av NSERC.  Ett nätverk är en oriktad graf som är inbäddad i Euclidean planet och vars kanter viktas med sin Euclidean längd. Vi säger en punkt p ligger på ett 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 längder (1 − λ) · l och λ · l för något värde λ  och [0, 1]. Genom att ange punkterna på G i fråga om deras relativa position (uttryckt med λ) längs deras innehållande kant, undviker vi alla tvetydigheter vid korsningar. Nätverksavståndet mellan två punkter p och q på ett nätverk G är längden på en vägd kortaste väg från p till q i G. Vi betecknar nätverksavståndet mellan p och q genom d G (p, q) och vi utelämnar subskriptet när nätverket förstås. Det största nätverksavståndet mellan två punkter på G är Termen kontinuerlig skiljer detta begrepp från den diskreta diametern som mäter det största nätverksavståndet mellan två hörn. Vi betecknar det euklideiska avståndet mellan p och q genom PQ. En linjesegment pq, med Vi utökar ett nätverk G med en genväg pq enligt följande. Vi introducerar nya hörn vid p och vid q i G, subdividera deras innehållande kanter, och vi lägger till en kant från p till q av längd. Det resulterande nätverket betecknas med G + pq. Vi försöker minimera den kontinuerliga diametern på ett nätverk genom att införa genvägar. I den diskreta abstrakta inställningen överväger vi en abstrakt graf G med enhetsvikter och frågar om vi kan minska den diskreta diametern av G till som mest D genom att lägga till i de flesta k kanter. För varje fast D ≥ 2, detta problem är NP-hård [1, 6, 8], har parametrisk komplexitet W[2]-hård [3, 4], och förblir NP-hård även om G är ett träd [1]. För en översikt över approximationsalgoritmer i termer av både D och k hänvisas till exempelvis Frati et al. Kommissionens genomförandeförordning (EU) nr 668/2014 av den 13 juni 2014 om tillämpningsföreskrifter för Europaparlamentets och rådets förordning (EU) nr 1151/2012 om kvalitetsordningar för jordbruksprodukter och livsmedel (EUT L 179, 19.6.2014, s. 1). I den diskreta geometriska inställningen överväger vi en geometrisk graf, där en genväg förbinder två hörn. Große m.fl. [5] är de första att överväga diameter minimering i denna inställning. De bestämmer en genväg som minimerar den diskreta diametern på en väg med n hörn i O(n log 3 n) tid. Ett geometriskt näts spännvidd, dvs. det största förhållandet mellan nätavståndet och Euclideans avstånd mellan två punkter, har också betraktats som målfunktion för kantförstärkning.  Våra resultat gäller nätverk som är banor, cykler och konvexa cykler. Figurerna 1 och 2 illustrerar exempel på optimala genvägar för vägar och cykler. I Avsnitt 2, utvecklar vi en algoritm som producerar en optimal genväg för en väg med n hörn i O(n) tid. I Avsnitt 3, visar vi att för cyklar en enda genväg aldrig räcker för att minska diametern och att två genvägar alltid räcker. Vi karakteriserar par av optimala genvägar för konvexa och icke-konvexa cykler. Baserat på denna karakterisering utvecklar vi en algoritm i Avsnitt 4 som bestämmer ett optimalt par genvägar för en konvex cykel med n hörn i O(n) tid.  Betrakta en polygonal väg P i planet. Vi söker en genväg pq för en väg P som minimerar den kontinuerliga diametern av den utökade vägen P + pq, dvs., Följande notation illustreras i Figur 3. Låt s och e vara endpoints för P och låt p vara närmare s än q längs P, dvs d(s, p) < d (s, q). För a, b, P, låt P [a, b] betecknar delbanan från a till b längs P, och låt C (p, q) vara den enkla cykeln i P + pq. Förstärker en väg P med en genväg pq. Genväg skapar en cykel C(p, q) med sub-sökvägen från p till q längs P. Den längst bort punkten från p på denna cykel isp och q är längst bort från q på C(p, q). Avståndet d(q,p) mellanq ochp längs P matchar Euclideans avstånd mellan p och q, på grund av följande. När vi flyttar en punkt g från p till q längs genvägen pq, då den längst punkten till formen g längs C(p, q) rör sig från p till q reser samma avstånd som g, dvs., Pq. I enlighet med artikel 2.1 i genomförandeförordning (EU) nr 668/2014 ska kommissionen ges befogenhet att anta delegerade akter i enlighet med artikel 290 i fördraget om Europeiska unionens funktionssätt vad gäller tillämpningen av Europaparlamentets och rådets förordning (EU) nr 1151/2012 om kvalitetsordningar för jordbruksprodukter och livsmedel (EUT L 179, 19.6.2014, s. 1). Låt pq vara en genväg för P. Varje kontinuerlig diametrial väg i P + pq innehåller en endpoint P, utom när genvägen ansluter slutpunkterna för P. Bevis. Låt P vara en polygonal väg med slutpunkter s och e, och låt pq vara en genväg för P. Låt π vara en väg längs P + pq. När en endpoint av π ligger på P [s, p] eller på P [e, q], kan vi skapa en längre väg genom att förlänga π till s eller e. Antag att båda endpoints av π ligger på den enkla cykel C(p, q). Som illustreras i figur 4, Vi kan flytta endpoints av π vid samma hastighet moturs längs C(p, q) tills en av dem sammanfaller med p eller med q. Den resulterande vägen π har samma längd som π och kan förlängas av P [s, p] eller P [e, q] som skapar en längre väg än π, om inte s = p och e = q. Därför, för varje genväg pq andra än se, varje kontinuerlig diametrial väg i P + pq måste innehålla och endpoint P. Enligt Lemma 2.1, har vi följande tre kandidater för kontinuerlig diametrial vägar i det utökade nätverket P + pq, varav två illustreras i Figur 5. 1. Vad är det för fel på dig? Sökvägen U (p, q) från s till e via genvägen pq, 2. sökvägen S(p, q) från s till den längst bort belägna punkten från s på C(p, q) och 3. sökvägen E(p, q) från e till den längst bort belägna punkten från e på C(p, q). Låta vara längst punkten från p på C(p, q), och låtq vara längst punkten från q på C(p, q). betecknar slack mellan p ochq (och symmetriskt mellan p och q) längs C (p, q). Med denna notation har vi och vi kan uttrycka längden av U (p, q), S (p, q) och E (p, q) enligt följande. J.-L. De Carufel, C. Grimm, A. Maheshwari, och M. Smid Följande lemma kännetecknar vilken av stigarna U (p, q), S(p, q) och E(p, q) bestämmer diametern på P + pq. Notera att dessa fall överlappar exempelvis E (p, q) och S (p, q) Bevis. Påståendet följer, eftersom följande relationer är bevarade för  till { <, =, >}. Lemma 2.3. För varje väg P, Det finns en optimal genväg pq sådan att S (p, q) och Bevis. Antag att vi har en genväg pq för en väg P sådan att U (p, q) är kontinuerlig diametrial i P + pq. I noteringen av Lemma 2.2 betyder detta z ≤ x och z ≤ y. Genom triangeln ojämlikhet, längden på U (p, q)-och därmed, den kontinuerliga diametern minskar eller förblir densamma som vi flyttar p närmare s (minskning x) eller q närmare e (minskning y). Dessutom ökar minskningen av x eller y z. Därför kan vi flytta genvägen närmare s och till e tills vi har x = z eller y = z, d.v.s., min(x, y, z) = min(x, y) samtidigt som vi behåller eller minskar den kontinuerliga diametern.
I den geometriska och kontinuerliga inställningen REF, är uppgiften att minimera den kontinuerliga diametern på ett geometriskt nätverk genom att infoga linjesegment som kan ansluta två punkter längs kanterna.
Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}