Polygonpartition

I geometri är en partition av en polygon en uppsättning primitiva enheter (t.ex. kvadrater), som inte överlappar varandra och vars förening är lika med polygonen. Ett polygonpartitionsproblem är ett problem med att hitta en partition som är minimal i någon mening, till exempel en partition med ett minsta antal enheter eller med enheter med minsta totala sidolängd.

Polygonpartitionering är en viktig klass av problem inom beräkningsgeometri . Det finns många olika polygonpartitionsproblem, beroende på vilken typ av polygon som partitioneras och på vilka typer av enheter som är tillåtna i partitionen.

Termen polygonnedbrytning används ofta som en allmän term som inkluderar både polygontäckning och partitionering.

Ansökningar

Polygonnedbrytning tillämpas på flera områden:

Mönsterigenkänningstekniker extraherar information från ett objekt för att beskriva, identifiera eller klassificera det. En etablerad strategi för att känna igen ett allmänt polygonalt objekt är att dekomponera det i enklare komponenter, sedan identifiera komponenterna och deras inbördes samband och använda denna information för att bestämma formen på objektet.
I VLSI- konstverksdatabehandling representeras layouter som polygoner, och ett tillvägagångssätt för att förbereda för elektronstrålelitografi är att sönderdela dessa polygonområden till grundläggande figurer. Polygonnedbrytning används också i processen att dela upp routingområdet i kanaler.
Inom beräkningsgeometri är algoritmer för problem på allmänna polygoner ofta mer komplexa än de för begränsade typer av polygoner som konvexa eller stjärnformade. Point -in-polygon-problemet är ett exempel. En strategi för att lösa några av dessa typer av problem på allmänna polygoner är att dekomponera polygonen i enkla komponentdelar, lösa problemet på varje komponent med hjälp av en specialiserad algoritm och sedan kombinera de partiella lösningarna.
Andra tillämpningar inkluderar datakomprimering , databassystem , bildbehandling och datorgrafik .

Dela upp en polygon i trianglar

Det mest välstuderade polygonpartitionsproblemet är partitionering till ett minsta antal trianglar, även kallad triangulering . För en hålfri polygon med $n$ hörn kan en triangulering beräknas i tiden $\Theta (n)$ . För en polygon med hål finns en nedre gräns för $\Omega (n\log n)$ .

Ett relaterat problem är partitionering till trianglar med en minimal total kantlängd, även kallad minimiviktstriangulering .

Dela upp en polygon i pseudotrianglar

Samma två varianter av problemet studerades för fallet där bitarna skulle vara pseudotrianglar – polygoner som likt trianglar har exakt tre konvexa hörn. Varianterna är: partitionering till ett minsta antal pseodtrianglar och partitionering till pseudotrianglar med minimal total kantlängd.

Dela upp en rätlinjig polygon i rektanglar

En speciell underfamilj av polygonpartitionsproblem uppstår när den stora polygonen är en rätlinjig polygon (även kallad: ortogonal polygon). I det här fallet är den viktigaste komponentformen att överväga rektangeln .

Rektangulära partitioner har många applikationer. I VLSI- design är det nödvändigt att bryta ner masker till de enklare former som finns i litografiska mönstergeneratorer, och liknande masknedbrytningsproblem uppstår också i DNA -mikroarraydesign. Rektangulära partitioner kan förenkla faltningsoperationer vid bildbehandling och kan användas för att komprimera bitmappsbilder . Närbesläktade problem med matrisnedbrytning har tillämpats på strålterapiplanering , och rektangulära skiljeväggar har också använts för att designa sekvenser för självmontering av robotar.

Minimera antalet komponenter

Problemet med att minimera antalet komponentrektanglar är polynom: flera polynomtidsalgoritmer är kända. Se och för undersökningar.

Problemet med att partitionera en rätlinjig polygon till ett minsta antal kvadrater (i motsats till godtyckliga rektanglar) är NP-hårt .

Minimera den totala kantlängden

I vissa applikationer är det viktigare att minimera den totala längden på snitten (t.ex. för att minimera kostnaden för att utföra skiljeväggen, eller för att minimera mängden damm). Detta problem kallas rektangulär partitionering med minsta kantlängd . Det studerades först av Lingas, Pinter, Rivest och Shamir 1982. Körtidens komplexitet av detta problem beror helt på om den råa polygonen tillåts ha hål.

Om den råa polygonen är hålfri kan en optimal partition hittas i tiden ${\displaystyle O(n^{4})} ,$ där n är antalet hörn i polygonen. I specialfallet med en "histogrampolygon" förbättras komplexiteten till $O(n^{3})$ . Algoritmen använder dynamisk programmering och förlitar sig på följande faktum: om polygonen är hålfri, har den en partition med minsta längd där varje maximalt linjesegment innehåller en vertex på gränsen. Anledningen är att i vilken minimilängdspartition som helst kan varje maximalt linjesegment "skjutas" tills det träffar en av gränsens hörn, utan att den totala längden ändras. Därför finns det bara ${\displaystyle O(n^{2})}-$ kandidater för ett linjesegment i en optimal partition, och de kan kontrolleras effektivt med hjälp av dynamisk programmering.

Om den råa polygonen kan ha hål , även om de är degenererade hål (dvs enstaka punkter), är problemet NP-svårt. Detta kan bevisas genom reduktion från Planar SAT . För det fall där alla hål är enstaka punkter har flera konstantfaktorapproximationer utvecklats:

En (3+sqrt(3)) approximation i tid $O(n^{2})$ ;
En (3+sqrt(3)) approximation i tid $O(n\log {n})$ ;
A 4 approximation i tid $O(n\log {n})$ (mer allmänt, i d dimensioner, är det en $2d$ approximation i tid $O(dn\log {n})$ ),
A 3 approximation i tid $O(n^{4})$ ;
En approximation på 1,75 i tid $O(n^{5})$ $d {\displaystyle 2d-4+4/ d}$ mer allmänt, i d- dimensioner, är det en approximation i tid ${\displaystyle O(dn^{2d+1})} )$ ; den senare approximationen använder en begränsad variant av problemet som kallas giljotinpartitionering , där snitten måste vara giljotinsnitt (kant-till-kant-snitt).
Flera polynom-tidsapproximationsscheman med sofistikerade giljotinsnitt.

Minimera antalet tomma

I den här inställningen innehåller den stora polygonen redan några parvis osammanhängande rektanglar. Målet är att hitta en partition av polygonen i rektanglar så att varje originalrektangel finns i en av bitarna, och med förbehåll för detta är antalet "blanks" (bitar som inte innehåller en originalrektangel) så lite som möjlig. Följande resultat är kända:

Om den stora polygonen är en rektangel, så är alla hål rektanglar i varje maximalt arrangemang av n rektanglar, och deras antal är högst $n-\lceil 2{\sqrt {n }}-1\rceil$ , och det här är tight.
Om den stora polygonen är en rätlinjig polygon med T- reflexhörn, kan hålen, i varje maximalt arrangemang av n rektanglar, delas upp i högst $T+n-\lceil 2 {\sqrt {n}}-1\rceil$ rektanglar, och detta är tätt.

Dela upp en polygon i trapetser

I VLSI-konstbearbetningssystem krävs det ofta att en polygonal region delas upp i det minsta antalet trapetser med två horisontella sidor. En triangel med horisontell sida anses vara en trapets med två horisontella sidor varav den ena är degenererad. För en hålfri polygon med $n$ sidor, kan en minsta sådan partition hittas i tiden $O(n^{2})$ .

Om antalet trapetser inte behöver vara minimalt kan en trapetsformning hittas i tiden $O(n)$ , som en biprodukt av en polygontrianguleringsalgoritm .

Om polygonen innehåller hål är problemet NP-komplett, men en 3-approximation kan hittas i tiden $O(n\log n)$ .

Dela upp en polygon i konvexa fyrhörningar

En quadrilateralization eller en quadrangulation är en uppdelning i fyrhörningar .

Ett återkommande kännetecken för kvadranguleringsproblem är om Steiner-punkten är tillåten, dvs om algoritmen tillåts lägga till punkter som inte är hörn i polygonen. Att tillåta Steiner-poäng kan möjliggöra mindre divisioner, men då är det mycket svårare att garantera att divisionerna som hittas av en algoritm har minsta storlek.

Det finns linjära tidsalgoritmer för kvadrangulering av hålfria polygoner med Steiner-punkter, men de är inte garanterade att hitta en minsta partition.

Dela upp en polygon i m -goner

En generalisering av tidigare problem är uppdelningen i polygoner som har exakt m sidor, eller högst m sidor. Här är målet att minimera den totala kantlängden. Detta problem kan lösas i tidspolynom i n och m .

Dela upp en polygon i konvexa polygoner

Vid uppdelning av en allmän polygon i konvexa polygoner har flera syften studerats.

Minimera antalet komponenter

konvexa polygoner som möjligt, med endast den initiala polygonens hörn. Det finns exakta och ungefärliga algoritmer för detta problem.

Minimera antalet tomma

Den ursprungliga polygonen innehåller redan några parvis disjunkta konvexa figurer, och målet är att dela upp den i konvexa polygoner så att varje originalfigur finns i en av bitarna, och med förbehåll för detta, antalet "blanks" (bitar som innehåller ingen originalfigur) är så liten som möjligt. Om den stora polygonen är konvex, är alla hålen konvexa i varje maximalt arrangemang av n konvexa figurer, och deras antal är högst $2n-5$ , och detta är snävt.

Utjämning av yta och omkrets

Det rättvisa polygonpartitioneringsproblemet är att dela upp en (konvex) polygon i (konvexa) bitar med lika omkrets och lika yta (detta är ett specialfall av rättvis kakskärning ). Vilken konvex polygon som helst kan lätt skäras till valfritt antal n av konvexa bitar med en area på exakt 1/ n . Det är dock mer utmanande att se till att bitarna har både lika yta och lika omkrets. Det finns algoritmer för att lösa detta problem när antalet bitar är en potens av 2.

En generalisering av detta problem är när area- och omkretsmåtten ersätts med ett mått på kroppen respektive på polygonens gräns. Detta problem studerades för 2 och 3 stycken.

Det finns en ytterligare generalisering för att hantera hur många åtgärder som helst.

Mer allmänna komponentformer

Mer allmänna former av bitar har studerats, inklusive: spiralformer , stjärnpolygoner och monotona polygoner . Se för en undersökning.

Se även

Polygontäckning – ett relaterat problem där bitarna tillåts överlappa varandra.
Packningsproblem – ett relaterat problem där bitarna måste passa in i hela det stora föremålet men inte behöver täcka det helt.
Euklidiska plattsättningar av konvexa regelbundna polygoner – ett problem med att dela upp hela planet till enkla polygoner som rektanglar .
Kvadrering av kvadraten – ett problem med att partitionera en integral kvadrat med endast andra integral kvadrater.
Rymduppdelning
Kakelpussel – ett pussel för att packa flera givna bitar i en given större polygon.
Giljotinpartition