Relativt konvext skrov

Det relativa konvexa skrovet av en ändlig uppsättning punkter i en enkel polygon

I diskret geometri och beräkningsgeometri är det relativa konvexa skrovet eller det geodetiska konvexa skrovet en analog av det konvexa skrovet för punkterna inuti en enkel polygon eller en likriktbar enkel sluten kurva .

Definition

Låt $P$ vara en enkel polygon eller en likriktbar enkel sluten kurva, och låt $X$ vara vilken mängd som helst som omges av $P$ . En geodetik mellan två punkter i $P$ är en kortaste väg som förbinder dessa två punkter som håller sig helt inom $P$ . En delmängd $K$ av punkterna inuti $P$ sägs vara relativt konvexa, geodesiskt konvexa eller $P$ -konvexa om, för varannan punkt i $K$ , geodetiken mellan dem i $P$ håller sig inom $K$ . Sedan kan det relativa konvexa skrovet för $X$ definieras som skärningspunkten för alla relativt konvexa uppsättningar som innehåller $X$ .

svagt enkla polygonen med minsta omkrets i $P$ som omsluter $X$ . Detta var den ursprungliga formuleringen av relativt konvexa skrov, av Sklansky, Chazin & Hansen (1972) . Men denna definition kompliceras av behovet av att använda svagt enkla polygoner (intuitivt, polygoner där polygongränsen kan röra eller överlappa sig själv men inte korsa sig själv) istället för enkla polygoner när X $\displaystyle X}$ är frånkopplad och dess komponenter inte är alla synliga för varandra.

Speciella fall

Finita uppsättningar av punkter

Toussaint (1986) , som tillhandahöll en effektiv algoritm för konstruktionen av det relativa konvexa skrovet för ändliga uppsättningar av punkter inuti en enkel polygon . Med efterföljande förbättringar av tidsgränserna för två subrutiner, att hitta kortaste vägarna mellan frågepunkter i en polygon och polygontriangulering tar denna algoritm tid $O(p+n \log(p+n))$ på en ingång med $n$ punkter i en polygon med $p$ hörn. Den kan också underhållas dynamiskt i sublinjär tid per uppdatering.

Det relativa konvexa skrovet för en ändlig uppsättning punkter är alltid en svagt enkel polygon , men det kanske inte är en enkel polygon, eftersom delar av den kan kopplas till varandra genom linjesegment eller polygonala banor snarare än genom områden med en area som inte är noll .

Enkla polygoner

För relativt konvexa skrov av enkla polygoner kan en alternativ men likvärdig definition av konvexitet användas. En enkel polygon $P$ inom en annan enkel polygon $Q$ är relativt konvex eller $Q$ -konvex om varje linjesegment som ingår i $Q$ som förbinder två punkter i ${ \displaystyle P}$ ligger inom $P$ . Det relativa konvexa skrovet för en enkel polygon $P$ inom $Q$ kan definieras som skärningspunkten mellan alla $Q$ -konvexa polygoner som innehåller $P$ , som den minsta $Q$ -konvex polygon som innehåller $P$ , eller som den minimala omkretsen enkel polygon som innehåller $P$ och som ingår i $Q$ .

Klette (2010) generaliserar linjära tidsalgoritmer för det konvexa skrovet av en enkel polygon till det relativa konvexa skrovet för en enkel polygon inom en annan. Den resulterande generaliserade algoritmen är dock inte linjär tid: dess tidskomplexitet beror på kapslingsdjupet för vissa egenskaper hos en polygon i en annan. I detta fall är det relativa konvexa skrovet i sig en enkel polygon. Alternativa linjära tidsalgoritmer baserade på vägplanering är kända.

En liknande definition kan också ges för det relativa konvexa skrovet av två disjunkta enkla polygoner. Denna typ av skrov kan användas i algoritmer för att testa om de två polygonerna kan separeras i disjunkta halvplan genom en kontinuerlig linjär rörelse, och i datastrukturer för kollisionsdetektering av rörliga polygoner.

Högre dimensioner

Definitionen av relativa konvexa skrov baserat på minsta inneslutning sträcker sig inte till högre dimensioner, eftersom (även utan att vara omgiven av en yttre form) den minsta ytarea inneslutningen av en icke-konvex uppsättning generellt sett inte är konvex. För det relativa konvexa skrovet för en sammankopplad uppsättning inom en annan uppsättning kan emellertid en definition liknande en för enkla polygoner användas. I detta fall kan en relativt konvex uppsättning återigen definieras som en delmängd av den givna yttre uppsättningen som innehåller alla linjesegment i den yttre uppsättningen mellan par av dess punkter. Det relativa konvexa skrovet kan definieras som skärningspunkten mellan alla relativt konvexa uppsättningar som innehåller den inre uppsättningen.