Opak set

Fyra ogenomskinliga set för en enhetsruta . Övre vänster: dess gräns, längd 4. Övre höger: Tre sidor, längd 3. Nedre vänster: ett Steinerträd av hörnen, längd

1+{\sqrt {3}}\approx 2.732

. Nedre höger: den förmodade optimala lösningen, längd

{\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639

.

I diskret geometri är en ogenomskinlig uppsättning ett system av kurvor eller annan uppsättning i planet som blockerar alla siktlinjer över en polygon , cirkel eller annan form. Ogenomskinliga uppsättningar har också kallats barriärer , stråldetektorer , ogenomskinliga lock , eller (i fall där de har formen av en skog av linjesegment eller andra kurvor) ogenomskinliga skogar . Ogenomskinliga set introducerades av Stefan Mazurkiewicz 1916, och problemet med att minimera deras totala längd ställdes av Frederick Bagemihl 1959.

Till exempel kan sikten genom en enhetsruta blockeras av dess fyra gränskanter, med längd 4, men en kortare ogenomskinlig skog blockerar sikten över torget med längden ${\sqrt {2}} +{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639$ . Det är obevisat om detta är den kortaste möjliga ogenomskinliga uppsättningen för kvadraten, och för de flesta andra former förblir detta problem likaledes olöst. Den kortaste ogenomskinliga uppsättningen för alla avgränsade konvexa uppsättningar i planet har högst längden omkretsen av uppsättningen och minst halva omkretsen. För kvadraten är en något starkare nedre gräns än halva omkretsen känd. En annan konvex uppsättning vars ogenomskinliga uppsättningar vanligtvis studeras är enhetscirkeln , för vilken den kortaste anslutna opaka uppsättningen har längden $2+\pi$ . Utan antagandet om anslutning har den kortaste ogenomskinliga uppsättningen för cirkeln en längd på minst $\pi$ och högst $4,7998$ .

Flera publicerade algoritmer som påstår sig hitta den kortaste ogenomskinliga uppsättningen för en konvex polygon visade sig senare vara felaktiga. Ändå är det möjligt att hitta en ogenomskinlig uppsättning med ett garanterat approximationsförhållande i linjär tid , eller att beräkna delmängden av planet vars synlighet blockeras av ett givet system av linjesegment i polynomtid .

Definitioner

Varje uppsättning $S$ i planet blockerar sikten genom en superset av $S$ , dess täckning $C$ . $C$ består av punkter för vilka alla linjer genom punkten skär $S$ . Om en given uppsättning $K$ bildar en delmängd av täckningen av $S$ , så sägs $S$ vara en ogenomskinlig uppsättning , barriär , stråldetektor eller ogenomskinlig täckning för $K$ . Om dessutom $S$ har en speciell form, bestående av ändligt många linjesegment vars förening bildar en skog , kallas det en ogenomskinlig skog . Det finns många möjliga ogenomskinliga uppsättningar för varje given uppsättning $K$ , inklusive $K$ själv, och många möjliga ogenomskinliga skogar. För ogenomskinliga skogar, eller mer allmänt för system med likriktbara kurvor , kan deras längd mätas på standard sätt. För mer generella punktsatser kan ettdimensionellt Hausdorff-mått användas, och överensstämmer med standardlängden vid linjesegment och likriktbara kurvor.

Mest forskning om detta problem antar att den givna mängden $K$ är en konvex mängd . När den inte är konvex utan bara en ansluten uppsättning , kan den ersättas med dess konvexa skrov utan att ändra dess ogenomskinliga uppsättningar. Vissa varianter av problemet begränsar den ogenomskinliga uppsättningen till att ligga helt innanför eller helt utanför $K$ . I det här fallet kallas det en inre barriär respektive en yttre barriär . När detta inte är specificerat antas barriären inte ha några begränsningar för sin placering. Versioner av problemet där den ogenomskinliga uppsättningen måste anslutas eller bilda en enda kurva har också övervägts. Det är inte känt om varje konvex uppsättning $P$ har en kortast ogenomskinlig uppsättning, eller om längden på dess opaka uppsättningar istället kan närma sig ett infimum utan att någonsin nå det. Varje ogenomskinlig uppsättning för $P$ kan approximeras godtyckligt nära i längd av en ogenomskinlig skog, och det har antagits att varje konvex polygon har en ogenomskinlig skog som sin kortaste ogenomskinliga uppsättning, men detta har inte bevisats.

Gräns

När området som ska täckas är ett konvext set måste längden på dess kortaste ogenomskinliga set vara minst halva dess omkrets och högst dess omkrets. För vissa regioner kan ytterligare förbättringar av dessa gränser göras.

Övre gräns

Om $K$ är en avgränsad konvex mängd som ska täckas, så bildar dess gräns $\partial K$ en ogenomskinlig mängd vars längd är omkretsen $|\partial K|$ . Därför är den kortaste möjliga längden på ett ogenomskinligt set högst omkretsen. För uppsättningar $K$ som är strikt konvexa, vilket innebär att det inte finns några linjesegment på gränsen, och för inre barriärer är denna gräns snäv. Varje punkt på gränsen måste ingå i den ogenomskinliga uppsättningen, eftersom varje gränspunkt har en tangentlinje genom sig som inte kan blockeras av några andra punkter. Samma resonemang visar att för inre barriärer av konvexa polygoner måste alla hörn inkluderas. Därför är det minsta Steinerträdet av hörnen den kortaste anslutna ogenomskinliga uppsättningen, och den resande försäljarvägen för hörnen är den kortaste enkurva ogenomskinliga uppsättningen. För inre barriärer av icke-polygonala konvexa uppsättningar som inte är strikt konvexa, eller för barriärer som inte behöver anslutas, kan andra ogenomskinliga uppsättningar vara kortare; till exempel är det alltid möjligt att utelämna det längsta linjesegmentet på gränsen. I dessa fall ger omkretsen eller Steinerträdets längd en övre gräns för längden av en ogenomskinlig uppsättning.

Nedre gräns

Det finns flera bevis på att en ogenomskinlig uppsättning för varje konvex uppsättning $K$ måste ha minst total längd $|\partial K|/2$ , halva omkretsen. En av de enklaste involverar Crofton-formeln , enligt vilken längden på en kurva är proportionell mot dess förväntade antal skärningspunkter med en slumpmässig linje från en lämplig sannolikhetsfördelning på linjer. Det är bekvämt att förenkla problemet genom att approximera $K$ med en strikt konvex supermängd, som kan väljas för att ha omkretsen godtyckligt nära den ursprungliga uppsättningen. Sedan, förutom tangentlinjerna till $K$ (som bildar en försvinnande del av alla linjer), korsar en linje som skär $K$ sin gräns två gånger. Därför, om en slumpmässig linje skär $K$ med sannolikheten $p$ , är det förväntade antalet gränsövergångar $2p$ . Men varje linje som skär $K$ skär sin ogenomskinliga mängd, så det förväntade antalet skärningar med den ogenomskinliga mängden är minst ${\displaystyle p} ,$ vilket är minst hälften av det för $K$ . Enligt Crofton-formeln har längderna på gränsen och barriären samma proportion som dessa förväntade tal.

Denna nedre gräns för $|\partial K|/2$ på längden av en ogenomskinlig uppsättning kan inte förbättras till att ha en större konstant faktor än 1/2, eftersom det finns exempel på konvexa uppsättningar som har ogenomskinliga uppsättningar vars längd är nära denna nedre gräns. I synnerhet för mycket långa tunna rektanglar bildar en långsida och två kortsidor en barriär, med total längd som kan göras godtyckligt nära halva omkretsen. Därför, bland lägre gränser som endast tar hänsyn till täckningsområdets omkrets, är gränsen för $|\partial K|/2$ är bäst möjligt. Men närmar sig $|\partial K|/2$ på detta sätt innebär att man överväger en sekvens av former snarare än bara en enda form, eftersom för varje konvex uppsättning $K$ som inte är en triangel, finns det en $\delta$ så att alla opaka uppsättningar har minst en längd $|\partial K|/2+\delta$ .

Specifika former

För en triangel , som för alla konvexa polygoner, är den kortaste anslutna ogenomskinliga uppsättningen dess minsta Steiner-träd. I fallet med en triangel kan detta träd beskrivas explicit: om triangelns bredaste vinkel är $2\pi /3$ (120°) eller mer, använder det de två kortaste kanterna på triangeln, och i övrigt består den av tre linjesegment från hörnen till triangelns Fermat-punkt . Men utan att anta anslutning har Steinerträdets optimalitet inte visats. Izumi har bevisat en liten förbättring av den perimeterhalverande nedre gränsen för den liksidiga triangeln .

Olöst problem i matematik :

Vilka är de kortaste ogenomskinliga uppsättningarna för enhetens kvadrat och enhetscirkel?

(fler olösta problem i matematik)

För en enhetskvadrat är omkretsen 4, omkretsen minus den längsta kanten är 3, och längden på det minsta Steinerträdet är $1+{\sqrt {3}}\approx 2.732$ . En kortare, frånkopplad ogenomskinlig skog är dock känd, med längden ${\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2,639$ . Den består av det minsta Steinerträdet av tre av kvadratens hörn, tillsammans med ett linjesegment som förbinder den fjärde vinkeln med mitten. Ross Honsberger krediterar sin upptäckt till Maurice Poirier, en kanadensisk lärare, men den beskrevs redan 1962 och 1964 av Jones. Det är känt för att vara optimalt bland skogar med bara två komponenter, och har antagits vara det bästa möjliga mer generellt, men detta är fortfarande obevisat. Den omkretshalverande nedre gränsen på 2 för kvadraten, som redan bevisats av Jones, kan förbättras något, till ${\displaystyle 2,00002} ,$ för varje barriär som består av högst uträkneligt många likriktbara kurvor , vilket förbättrar liknande tidigare gränser som begränsat barriär placeras endast nära den givna rutten.

Ogenomskinliga skogar för en enhetscirkel. Vänster: den U-formade optimala anslutna barriären, med längden

2+\pi

. Höger: Den mest kända barriären, med tre komponenter och längd

\approx 4.7998

.

Fallet med enhetscirkeln beskrevs i en kolumn i Scientific American från 1995 av Ian Stewart , med en lösning av längden ${\displaystyle 2+\pi },$ optimal för en enkel kurva eller ansluten barriär men inte för en ogenomskinlig skog med flera kurvor. Vance Faber och Jan Mycielski tillskriver Menachem Magidor denna enkelkurva lösning 1974. År 1980 hade E. Makai redan tillhandahållit en bättre trekomponentslösning, med längden cirka ${\displaystyle 4,7998} ,$ återupptäckt av John Day i en uppföljning till Stewarts kolumn. Den okända längden på den optimala lösningen har kallats stråldetekteringskonstanten .

Algoritmer

Två publicerade algoritmer gör anspråk på att generera den optimala ogenomskinliga skogen för godtyckliga polygoner, baserat på idén att den optimala lösningen har en speciell struktur: ett Steinerträd för en triangel i en triangulering av polygonen och ett segment i varje kvarvarande triangel från en vertex till motsatt sida, av längd lika med triangelns höjd. Denna struktur matchar den förmodade strukturen för den optimala lösningen för en kvadrat. Även om den optimala trianguleringen för en lösning av denna form inte är en del av indata till dessa algoritmer, kan den hittas av algoritmerna i polynomtid med hjälp av dynamisk programmering . Dessa algoritmer löser dock inte problemet korrekt för alla polygoner, eftersom vissa polygoner har kortare lösningar med en annan struktur än de de hittar. I synnerhet för en lång tunn rektangel är det minsta Steinerträdet av alla fyra hörn kortare än den trianguleringsbaserade lösningen som dessa algoritmer hittar. Ingen känd algoritm har garanterats hitta en korrekt lösning på problemet, oavsett dess drifttid.

Trots detta bakslag kan den kortaste enkurvabarriären för en konvex polygon, som är den resande försäljarens väg för dess hörn, beräknas exakt i polynomtid för konvexa polygoner med en dynamisk programmeringsalgoritm , i beräkningsmodeller för vilka summor av radikaler kan beräknas exakt. Det har också gjorts mer framgångsrika studier av approximationsalgoritmer för problemet och för att bestämma täckningen av en given barriär.

Approximation

Med de allmänna gränserna för ogenomskinlig skogs längd i termer av omkrets, närmar omkretsen av en konvex uppsättning sin kortaste ogenomskinliga skog till inom en faktor två i längd. I två artiklar tillhandahåller Dumitrescu, Jiang, Pach och Tóth flera linjära tidsapproximationsalgoritmer för den kortaste opaka uppsättningen för konvexa polygoner, med bättre approximationsförhållanden än två:

För allmänna ogenomskinliga uppsättningar tillhandahåller de en algoritm vars approximationsförhållande är högst ${\frac {1}{2}}+{\frac {2+{\sqrt {2}}}{\pi }}\approx 1,5868.$ Den allmänna idén med algoritmen är att konstruera en "båge och pil"-liknande barriär från den minsta perimetergränsen för ingången, bestående av en polygonal kedja sträckt runt polygonen från ett hörn av begränsningsrutan till det motsatta hörnet, tillsammans med ett linjesegment som förbinder ett tredje hörn av begränsningsrutan med rutans diagonal.
För ogenomskinliga uppsättningar som består av en enda båge tillhandahåller de en algoritm vars approximationsförhållande är högst ${\frac {\pi +5}{\pi +2}}\approx 1,5835.$ Den resulterande barriären definieras av en stödjande linje av inmatningsformen. Ingången skjuter ut vinkelrätt på ett intervall av denna linje, och barriären förbinder de två ändpunkterna av detta intervall med en U-formad kurva sträckt snäv runt ingången, som den optimala anslutna barriären för en cirkel. Algoritmen använder roterande bromsok för att hitta den stödlinje för vilken längden på den resulterande barriären minimeras.
För anslutna opaka uppsättningar tillhandahåller de en algoritm vars approximationsförhållande är högst $1,5716$ . Denna metod kombinerar enkelbågsbarriären med specialbehandling för former som är nära en liksidig triangel , för vilken triangelns Steinerträd är en kortare ansluten barriär.
För inre barriärer tillhandahåller de en algoritm vars approximationsförhållande är högst $1,7168$ . Tanken är att använda en generalisering föreslagen av Shermer av strukturen för de felaktiga tidigare algoritmerna (ett Steinerträd på en delmängd av punkterna, tillsammans med höjdsegment för en triangulering av den återstående inmatningen), med en snabb approximation för Steinerträdet del av approximationen.

Dessutom, eftersom den kortaste anslutna inre barriären av en konvex polygon ges av det minsta Steinerträdet, har den ett polynom-tidsapproximationsschema .

Rapportering

Regionen som täcks av en viss skog kan bestämmas enligt följande:

Hitta det konvexa skrovet för varje ansluten komponent i skogen.
För varje vertex $p$ i skrovet, svepa en linje cirkulärt runt $p$ , och dela upp planet i kilar inom vilka sveplinjen korsar ett av skroven och kilar inom vilka sveplinjen korsar planet utan hinder. Föreningen av de täckta kilarna bildar en uppsättning $C_{p}$ .
Hitta skärningspunkten för alla mängderna $C_{p}$ . Denna korsning är täckningen av skogen.

Om ingången består av $n$ linjesegment som bildar $m$ anslutna komponenter, så består var och en av de $n$ uppsättningarna $C_{p}$ av högst $2m$ kilar. Det följer att täckningsområdets kombinatoriska komplexitet, och tiden för att konstruera det, är $O(m^{2}n^{2})$ som uttrycks i big O-notation .

Även om den är optimal i värsta fall för indata vars täckningsområde har en kombinatorisk komplexitet som matchar denna gräns, kan denna algoritm förbättras heuristiskt i praktiken genom en förbearbetningsfas som slår samman överlappande par av skrov tills alla återstående skrov är osammanhängande, i tid O $O(n\log ^{2}n)$ . Om detta minskar inmatningen till ett enda skrov behöver den dyrare svepnings- och skärningsalgoritmen inte köras: i detta fall är skrovet täckningsområdet.

Kurvfria ogenomskinliga set

De första fyra stegen i en konstruktion av Bagemihl för fraktal ogenomskinliga uppsättningar för enhetstorget

Mazurkiewicz (1916) visade att det är möjligt för en ogenomskinlig uppsättning att undvika att innehålla några icke-triviala kurvor och fortfarande ha ändlig total längd. En förenklad konstruktion av Bagemihl (1959), som visas i figuren, ger ett exempel på enhetskvadraten. Konstruktionen börjar med linjesegment som bildar en ogenomskinlig uppsättning med en extra egenskap: segmenten med negativ lutning blockerar alla linjer med icke-negativ lutning, medan segmenten med positiv lutning blockerar alla linjer med icke-positiv lutning. I figuren är de initiala segmenten med denna egenskap fyra disjunkta segment längs kvadratens diagonaler. Sedan delar den upp dessa segment upprepade gånger samtidigt som den här egenskapen bibehålls. På varje nivå av konstruktionen delas varje linjesegment av en liten lucka nära dess mittpunkt i två linjesegment, med lutning av samma tecken, som tillsammans blockerar alla linjer i det motsatta tecknet som blockerades av det ursprungliga linjesegmentet. Gränsuppsättningen för denna konstruktion är ett Cantor-utrymme som, liksom alla mellanstadier av bygget , är en ogenomskinlig uppsättning för torget. Med snabbt minskande gapstorlekar producerar konstruktionen en uppsättning vars Hausdorff-dimension är en, och vars endimensionella Hausdorff-mått (ett begrepp om längd som är lämpligt för sådana uppsättningar) är ändligt.

Avståndsmängderna för gränsen för en kvadrat, eller av den fyra-segments kortaste kända opaka uppsättningen för kvadraten, innehåller båda alla avstånd i intervallet från 0 till 2 $\displaystyle {\sqrt {2}}}$ . Men genom att använda liknande fraktala konstruktioner är det också möjligt att hitta fraktala ogenomskinliga uppsättningar vars avståndsuppsättningar utelämnar oändligt många av avstånden i detta intervall, eller som (förutsatt kontinuumhypotesen) bildar en uppsättning mått noll .

Historia

Ogenomskinliga uppsättningar studerades ursprungligen av Stefan Mazurkiewicz 1916. Andra tidiga arbeten om ogenomskinliga uppsättningar inkluderar uppsatser av HM Sen Gupta och NC Basu Mazumdar 1955, och av Frederick Bagemihl 1959, men dessa handlar i första hand om avståndsuppsättningarna och topologiska egenskaper hos barriärer snarare än att minimera deras längd. I ett efterskrift till sin tidning bad Bagemihl om minsta längd på en inre barriär för torget, och efterföljande arbete har till stor del fokuserat på versioner av problemet med längdminimering. De har upprepade gånger poserats, med flera färgglada formuleringar: gräva ett dike av så kort längd som möjligt för att hitta en rak nedgrävd telefonkabel, försök att hitta en närliggande rak väg när de gick vilse i en skog, simma till en rak strandlinje medan de förlorades kl. havet, måla väggar effektivt för att göra ett glashus ogenomskinligt, etc.

Problemet har också generaliserats till uppsättningar som blockerar all geodetik på ett Riemann-grenrör , eller som blockerar linjer genom uppsättningar i högre dimensioner. I tre dimensioner, frågar motsvarande fråga om en samling ytor med minsta totala yta som blockerar all synlighet över en solid. Men för vissa fasta ämnen, såsom en boll, är det inte klart om en sådan samling finns, eller om området istället har ett infimum som inte kan uppnås.

Se även