Polygonalisering

16 polygonaliseringar av en uppsättning av sex punkter

I beräkningsgeometri är en polygonalisering av en ändlig uppsättning punkter i det euklidiska planet en enkel polygon med de givna punkterna som sina hörn. En polygonalisering kan också kallas en polygonisering , enkel polygonalisering , Hamiltonsk polygon , icke-korsande Hamilton-cykel eller korsningsfri rak-kant-spännande cykel .

Varje punktmängd som inte ligger på en enda linje har minst en polygonalisering, som kan hittas i polynomtid. För punkter i konvex position finns det bara en, men för vissa andra punktuppsättningar kan det vara exponentiellt många. Att hitta en optimal polygonalisering under flera naturliga optimeringskriterier är ett svårt problem, inklusive som ett specialfall problemet med resande säljare . Komplexiteten i att räkna alla polygonaliseringar är fortfarande okänd.

Definition

En polygonalisering är en enkel polygon som har en given uppsättning punkter i det euklidiska planet som sin uppsättning av hörn. En polygon kan beskrivas med en cyklisk ordning på dess hörn, som är förbundna i på varandra följande par av linjesegment, polygonens kanter. En polygon, definierad på detta sätt, är "enkel" om de enda skärningspunkterna för dessa linjesegment är vid delade ändpunkter.

Vissa författare överväger bara polygonaliseringar för punkter som är i allmän position , vilket betyder att inga tre är på en linje. Med detta antagande kan vinkeln mellan två på varandra följande segment av polygonen inte vara 180°. Men när punktuppsättningar med kollineariteter beaktas, är det i allmänhet tillåtet att deras polygonaliseringar har 180° vinklar vid vissa punkter. När detta händer anses dessa punkter fortfarande vara hörn, snarare än att vara innanför kanterna.

Existens

Polygonaliseringar av ett 3 × 3 rutnät. De 180° vinklar som är synliga i varje polygon är nödvändiga: för ett rutnät av denna storlek har alla polygonaliseringar en 180° vinkel.

Steinhaus (1964) observerade att varje finit punktmängd utan tre på en linje bildar hörn av en enkel polygon. Men att kräva att ingen tre ska stå i rad är onödigt starkt. Istället är allt som krävs för att det ska finnas en polygonalisering (som tillåter 180° vinklar) att punkterna inte alla ligger på en linje. Om de inte gör det har de en polygonalisering som kan konstrueras i polynomtid . Ett sätt att konstruera en polygonalisering är att välja valfri punkt $q$ i det konvexa skrovet av $P$ (inte nödvändigtvis en av de givna punkterna). En radiell ordning av punkterna runt $q$ (bryter banden efter avstånd från q) ger den cykliska ordningen för en stjärnformad polygon genom alla givna punkter, med $q$ i dess kärna. Samma idé att sortera punkter radiellt runt en central punkt används i vissa versioner av Graham scan konvexa skrovalgoritmen och kan utföras i $O(n\log n)$ tid. Polygonaliseringar som undviker 180° vinklar finns inte alltid. Till exempel, för 3 × 3 och 5 × 5 kvadratiska rutnät använder alla polygonaliseringar 180° vinklar.

Förutom stjärnformade polygonaliseringar har varje icke-kollinjär uppsättning punkter en polygonalisering som är en monoton polygon . Detta betyder att, med avseende på någon rät linje (som kan tas som $x$ -axeln) skär varje vinkelrät linje mot referenslinjen polygonen i ett enda intervall, eller inte alls. En konstruktion av Grünbaum (1994) börjar med att sortera punkterna efter deras $x$ -koordinater och dra en linje genom de två extrempunkterna. Eftersom punkterna inte är alla i en linje, måste minst ett av de två öppna halvplanen som begränsas av denna linje vara tom. Grünbaum bildar två monotona polygonala kedjor som förbinder extrempunkterna genom sorterade undersekvenser av punkterna: en för punkterna i detta icke-tomma öppna halvplan och den andra för de återstående punkterna. Deras förening är den önskade monotona polygonen. Efter sorteringssteget kan resten av konstruktionen utföras i linjär tid .

Det är NP-komplett att bestämma om en uppsättning punkter har en polygonalisering med endast axelparallella kanter. Polygonaliseringar med den ytterligare begränsningen att de gör en högersväng vid varje hörn, om de finns, är dock unikt bestämda. Varje axelparallell linje genom en punkt måste passera genom ett jämnt antal punkter, och denna polygonalisering måste koppla samman alternerande par av punkter på denna linje. Polygonaliseringen kan hittas i tiden $O(n\log n)$ genom att gruppera punkterna efter lika koordinater och sortera varje grupp efter den andra koordinaten. För varje punktuppsättning kan högst en rotation ha en polygonalisering av denna form, och denna rotation kan återigen hittas i polynomtid.

Optimering

Olöst problem i matematik :

Vad är beräkningskomplexiteten för den längsta polygonaliseringen?

(fler olösta problem i matematik)

Problem med att hitta en optimal polygonalisering (för olika kriterier för optimalitet) är ofta beräkningsmässigt omöjliga. Till exempel har lösningen på resandeförsäljarproblemet, för de givna punkterna, inga korsningar. Därför är det alltid en polygonalisering, polygonaliseringen med minsta omkrets . Det är NP-svårt att hitta. På liknande sätt är det känt att det är NP-hårt att hitta den enkla polygonaliseringen med minimal eller maximal area och har varit föremål för vissa beräkningsansträngningar. Den maximala arean är alltid mer än hälften av arean av det konvexa skrovet , vilket ger ett approximationsförhållande på 2. Den exakta komplexiteten för den enkla polygonaliseringen med maximal omkrets, och förekomsten av ett konstant approximationsförhållande för detta problem, förblir okänd. Polygonaliseringen som minimerar längden på dess längsta kant är också NP-svår att hitta och svår att approximera till ett approximationsförhållande bättre än ${\sqrt {3}}$ ; ingen approximation av konstant faktor är känd.

En icke-optimal lösning på resandeförsäljarproblemet kan ha korsningar, men det är möjligt att eliminera alla korsningar genom lokala optimeringssteg som minskar den totala längden. Genom att använda steg som även eliminerar korsningar vid varje steg kan detta göras i polynomtid , men utan denna begränsning finns det lokala optimeringssekvenser som istället använder ett exponentiellt antal steg.

Den kortaste bitoniska turen (den minsta perimetern monotona polygonen genom de givna punkterna) är alltid en polygonalisering och kan hittas i polynomtid.

Räkning

Olöst problem i matematik :

Vad är beräkningskomplexiteten för att räkna polygonaliseringar?

(fler olösta problem i matematik)

Problemet med att räkna alla polygonaliseringar av en given punktmängd tillhör #P , klassen av räkneproblem förknippade med beslutsproblem i NP . Det är dock okänt om det är #P-komplett eller, om inte, vad dess beräkningskomplexitet kan vara. En uppsättning punkter har exakt en polygonalisering om och endast om den är i konvex position . Det finns uppsättningar av $n$ punkter för vilka antalet polygonaliseringar är så stort som $4,64^{n}$ , och varje uppsättning av $n$ punkter har högst ${ \displaystyle 54.6^{n}}$ polygonaliseringar.

Metoder som tillämpar planseparatorsatsen på märkta trianguleringar av punkterna kan användas för att räkna alla polygonaliseringar av en uppsättning av $n$ punkter i subexponentiell tid, $n^{O({\sqrt {n}})}$ . Dynamisk programmering kan användas för att räkna alla monotona polygonaliseringar i polynomtid, och resultaten av denna beräkning kan sedan användas för att generera en slumpmässig monoton polygonalisering.

Generation

Olöst problem i matematik :

Kan lokala drag koppla tillståndsutrymmet för polygonaliseringar för varje punktuppsättning?

(fler olösta problem i matematik)

En polygon som inte kan ändras till någon annan polygon genom samma punkter med flips eller VE-flips

Det är okänt om det är möjligt för systemet med alla polygonaliseringar att bilda ett anslutet tillståndsrum under lokala rörelser som ändrar ett begränsat antal av polygonaliseringarnas kanter. Om detta var möjligt skulle det kunna användas som en del av en algoritm för att generera alla polygonaliseringar, genom att tillämpa en grafövergång till tillståndsutrymmet. För detta problem är det otillräckligt att överväga flips som tar bort två kanter av en polygonalisering och ersätter dem med två andra kanter, eller VE-flips som tar bort tre kanter, varav två delar en vertex, och ersätter dem med tre andra kanter. Det finns polygonaliseringar för vilka ingen flip eller VE-flip är möjlig, även om samma punktuppsättning har andra polygonaliseringar.

De polygonala omslagen , svagt enkla polygoner som använder varje given punkt en eller flera gånger som en vertex, inkluderar alla polygonaliseringar och är sammankopplade med lokala drag. En annan mer allmän klass av polygoner, de omgivande polygonerna , är enkla polygoner som har några av de givna punkterna som hörn och omsluter alla punkter. De är återigen lokalt anslutna och kan listas i polynomtid per polygon. Algoritmen konstruerar ett träd av polygoner, med det konvexa skrovet som sin rot och med föräldern till varandra omgivande polygon som erhålls genom att ta bort en vertex (visat vara möjligt genom att applicera två öronsatsen på polygonens utsida). Den tillämpar sedan en omvänd sökningsalgoritm på detta träd för att lista polygonerna. Som en konsekvens av denna metod kan alla polygonaliseringar listas i exponentiell tid ( $2^{O(n)}$ för $n$ punkter) och polynomutrymme .

Ansökningar

Klassiska kopplingspunkter -pussel involverar att koppla ihop punkter i sekvens för att bilda en oväntad form, ofta utan korsningar. Problemet med resande säljare och dess varianter har många tillämpningar. Polygonalisering har också tillämpningar vid rekonstruktion av konturlinjer från spridda datapunkter och vid gränsspårning i bildanalys .

Se även

• Denjoy–Riesz-satsen , om mängder av oändligt många punkter som kan kopplas samman med en Jordanbåge