Verwijderen van punten in Delaunaytriangulaties

 
Verwijderen van punten in Delaunaytriangulaties
Als je algoritmen ontwerpt, kun je streven naar asymptotisch optimale algoritmen óf je ontwikkelt algoritmen die in de praktijk goed werken. Hoe zijn deze twee visies te verenigen? En welke algoritmen presteren zowel goed qua asymptotische analyse als in de praktijk?
Okke Schrijvers
In dit artikel kijk ik naar algoritmen voor Delaunay -triangulaties, waarbij we de plaatsbepaling van punten verbeteren door nabijgelegen punten in de datastructuur te gebruiken. In mijn Masterscriptie Insertions and Deletions in Delaunay Triangulations using Guided Point Location heb ik de twee belangrijkste aspecten onderzocht van Delaunay-triangulaties: de constructie van de Delaunay-triangulatie van een set punten, en het verwijderen van een punt uit een geconstrueerde Delaunay-triangulatie. In dit artikel bespreek ik alleen verwijderingen. Ik kijk eerst naar de denitie van Delaunay-triangulaties en de traditionele manier om een punt hieruit te verwijderen. Daarna behandel ik de manier waarop ik dit verbeterd heb, de asymptotische verbeteringen en uiteindelijk de experimentele resultaten.
Delaunay-triangulaties
Voor we de theorie in duiken, is het handig om te weten wat Delaunay-triangulaties zijn. Laten we eerst naar de meetkundige denitie kijken. Een triangulatie van een set S punten in het vlak, is een partitie van het vlak in driehoeken waarbij de hoekpunten van elke driehoek uit de set S komen. De triangulatie van een set punten is niet uniek, de Delaunay-triangulatie is een specieke triangulatie waarbij voor elke driehoek geldt dat de omgeschreven cirkel geen enkel ander punt uit S bevat (figuur 1). De Delaunay-triangulatie is wel uniek (onder bepaalde aannames) en een driehoek is onderdeel van de triangulatie als en alléén als er geen enkel ander punt in de omgeschreven cirkel ligt.
Figuur 1. Aan de linkerkant een puntset S en aan de rechterkant de Delaunaytriangulatie. De omschreven cirkel van elke driehoek is leeg
In de praktijk worden Delaunay-triangulaties voor verschillende doeleinden gebruikt; bijvoorbeeld voor de interpolatie van hoogtevelden. Wanneer een vliegtuig over land vliegt om hoogtemetingen te doen, kan deze slechts op een discreet aantal punten deze metingen verrichten. Om een continu hoogteveld te krijgen, worden vaak Delaunay-triangulaties gebruikt, waarbij de input een set van punten met de hoogte- en breedtegraad is. Nadat de Delaunay-triangulatie van de punten is gemaakt, kan de hoogte op elk punt worden bepaald door naar de driehoek te kijken die het punt bevat en barycentrische interpolatie te gebruiken.
Andere toepassingen liggen in de werktuigbouwkunde en (numerieke) wiskunde, waar Delaunay-triangulaties worden gebruikt in de eindige-elementenmethode om bijvoorbeeld de sterkte van bruggen en gebouwen mee te berekenen, en in computergraphics voor special effects.
Verwijderingen
Nadat een Delaunay-triangulatie is geconstrueerd, kan het zijn dat er bepaalde punten verwijderd moeten worden. In het geval van hoogtemetingen kan het bijvoorbeeld voorkomen dat er een meetfout is gemaakt die gecorrigeerd moet worden. Als we een punt q verwijderen uit een Delaunay-triangulatie van S U {q} is het niet nodig om de hele datastructuur opnieuw op te bouwen. Alle driehoeken waar punt q onderdeel van is verdwijnen, maar alle andere driehoeken blijven bestaan. De reden hiervoor is simpel: aangezien de driehoek onderdeel is van de Delaunay-triangulatie van S U {q}, is er geen enkel punt uit S U {q} dat in de omgeschreven cirkel van de driehoek ligt. Dus is er ook geen punt uit S dat daarin ligt en daarom is het een driehoek in de nieuwe Delaunay-triangulatie. In de literatuur zijn verschillende manieren voorgesteld om een punt te verwijderen; interessant is de ‘Triangulate and Sew’-methode ofwel ‘trianguleer en naai’-methode (figuur 2). Aangezien alleen driehoeken die aan het punt qgrenzen verwijderd dienen te worden, blijft een een stervormige veelhoek over die opnieuw getrianguleerd dient te worden. Dit wordt gedaan door een nieuwe Delaunay-triangulatie te maken van alle incidente punten van q(alle punten waarvoor er een ribbe ofwel lijn naar qbestaat). De ‘binnenste’ driehoeken van deze triangulatie zijn onderdeel van de Delaunay-triangulatie van Sen kunnen in de oude triangulatie worden genaaid. De belangrijkste stap is het trianguleren van de incidente puntset P, wat gedaan kan worden door middel van gerandomiseerde incrementele constructie. De punten van de inputset worden hierbij in willekeurige volgorde aan een nieuwe Delaunay-triangulatie toegevoegd en na elke toevoeging hebben we de correcte Delaunay-triangulatie van alle toegevoegde punten. De tijdscomplexiteit van een incrementele constructie hangt af van de volgorde waarin de punten behandeld worden.
Figuur 2. De ‘Triangulate and Sew’-methode voor het verwijderen van een punt uit de Delaunaytriangulatie
Het voordeel van een gerandomiseerde incrementele constructie ten opzichte van een normale incrementele constructie is dat de kans op een slechte volgorde zeer klein is. Dit is belangrijk in de looptijdanalyse van het toevoegen van een punt aan de Delaunay-triangulatie. Het toevoegen van een punt, en daarmee de looptijdanalyse, kan worden opgedeeld in twee delen. Allereerst moet de driehoek worden gevonden waarin het nieuwe punt zich bevindt. Vervolgens moeten alle driehoeken die conflicteren met dit punt worden verwijderd en de nieuwe driehoeken worden toegevoegd. Het eerste wordt de plaatsbepaling genoemd, en dit kost O(log i) tijd wanneer er gebruik gemaakt wordt van een plaatsbepalingsdatastructuur. iis hierbij het aantal driehoeken in de reeds geconstrueerde datastructuur.
Het tweede gedeelte is de structurele complexiteit, en de exacte looptijd hiervan is moeilijker te bepalen. In twee dimensies kan worden aangetoond dat het verwachte aantal gecreëerde en verwijderde driehoeken in een gerandomiseerde incrementele constructie constant is. Voor driedimensionale Delaunay-triangulaties, die een vergelijkbare definitie hebben maar dan met tetraëders (oftewel viervlakken) en bollen, hangt de complexiteit af van de inputset en dit wordt vaak aangeduid met C(p) , wat ligt tussen constant en lineair in i. Over het hele constructieproces kost de plaatsbepaling hierdoor O(d log d) tijd (waarbij dde graad van q, oftewel de grootte van puntset Pis) en de structurele complexiteit voor een totale tijd van O( dlog d+ C( P)).
Onze methode
Wij verbeteren de Triangulate and Sew-methode op twee manieren (zie figuur 3) . Ten eerste reduceren we de plaatsbepaling van een enkel punt tot een constante-tijd operatie, wat leidt tot een totale tijd van O(d) voor de plaatsbepaling. Ten tweede tonen we aan dat wanneer we de volledige Delaunay-triangulatie van de puntset Pconstrueren, we een aantal driehoeken maken waarvan we van tevoren al kunnen stellen dat ze niet gebruikt zullen worden omdat ze geen onderdeel van de ‘binnenste’ driehoeken zijn. We stellen een nieuwe definitie voor die we de ‘ster Delaunay-triangulatie’ noemen, waarin we voorkomen dat deze driehoeken gecreëerd worden.
Figuur 3. De tijdcomplexiteit van Triangulate and Sew en onze verbeteringen hierin
Een overzicht van de methode geven we in figuur 4 . Om de nieuwe triangulatie van de punten incident aan qte maken, verwijderen we ze eerst één voor één tot slechts drie punten overblijven, dan verwijderen we qen bouwen de triangulatie opnieuw op. In de komende secties wordt duidelijk waarom wij deze aanpak gebruiken.
Figuur 4. Een overzicht van onze aanpak. Om de nieuwe triangulatie van de punten incident aan q te maken, verwijderen we ze eerst één voor één tot slechts drie punten overblijven, dan verwijderen we q en bouwen de triangulatie opnieuw op.
Plaatsbepaling van een punt
We stellen voor de plaatsbepaling van een punt pi te versnellen door gebruik te maken van een ‘gidspunt’. Wanneer een punt word toegevoegd in een Delaunay-triangulatie bij Triangulate and Sew moet er gezocht worden naar de locatie van dat punt in de triangulatie. Hierbij wordt echter belangrijke informatie niet gebruikt: de connectiviteit van punten in de originele triangulatie. Als we een pointer hebben naar een punt dat zich al in de Delaunay-triangulatie bevindt, hebben we geen extra zoekdatastructuur nodig en kunnen we de pointer naar de locatie in de datastructuur volgen. Vanaf dat moment moeten er twee dingen gedaan worden: ten eerste moeten we de driehoek vinden waar het lijnsegment tussen het punt pi en de gids voor pi in ligt en ten tweede moeten we het lijnsegment volgen om de driehoek te vinden waarin pi ligt. Om de tijdscomplexiteit te kunnen bepalen, moeten we een bovengrens vinden voor het aantal operaties dat deze stappen kosten. Dit doen we door te redeneren over het aantal driehoeken waarnaar gekeken moet worden. We beginnen met het volgen van het lijnsegment tussen pi en zijn gids. Als deze twee punten
incident zijn in de Delaunay-triangulatie nadat pi is toegevoegd, dan moeten alle driehoeken die het lijnsegment doorsnijden zijn verwijderd tijdens de toevoeging. Dit betekent dat we de kosten hiervoor kunnen toekennen aan de structurele complexiteit. Dit is zeer gewenst, dus we willen de gids zodanig kiezen dat dit het geval is. Om dit te doen moeten we wel zeker weten dat het lijnsegment gecreëerd wordt tijdens de toevoeging. Om dit te doen, nemen we alle punten die incident zijn aan qen projecteren die op een lagerdimensionele bol; dit noemen we de ‘oppervlak Delaunay-triangulatie’. In figuur 5 geven we een voorbeeld in twee dimensies: het punt qheeft zes incidente punten die geprojecteerd worden op een cirkel. De gidspunten worden bepaald door de punten één voor één van de oppervlak Delaunay-triangulatie te verwijderen en aangezien dit in een lagere dimensie is, is dit een goedkope operatie. Wanneer de juiste meetkundige predicaten worden gebruikt bij het verwijderen van punten op het oppervlak, is het resultaat hetzelfde als in de originele dimensie. Door deze transformatie is de operatie echter een stuk goedkoper, en kan worden aangetoond dat dit voor zowel 2D als 3D in constante tijd per punt gedaan kan worden, mits de graad van pi in de Delaunay-triangulatie (verwacht) constant is.
Figuur 5. De incidente punten van q in een tweedimensionale Delaunaytriangulatie kunnen op een cirkel worden geprojecteerd om zo een eendimensionale oppervlak Delaunaytriangulatie te krijgen
Dan resteert het vinden van de driehoek die het lijnsegment tussen pi en zijn gids doorsnijdt. Als we een gids kiezen met een constant aantal aangrenzende driehoeken, dan kunnen we elk van deze driehoeken bekijken in totaal constante tijd. Dit is het geval zolang de (verwachte) graad van de gids van pi constant is. We moeten dus een paar punten vinden, pi en zijn gids, die incident zijn in de oppervlak Delaunay-triangulatie en allebei een constante (verwachte) graad hebben. Hier zijn verschillende opties mogelijk:
• Kies pvolledig willekeurig en bewaar welke punten incident waren aan p. Aangezien pwillekeurig is, is het verwachte aantal incidente punten ten hoogste 6. Wanneer het punt pmoet worden toegevoegd aan de Delaunay-triangulatie, wordt het punt met de laagste graad gebruikt. In de scriptie wordt aangetoond dat de verwachte graad van dit punt constant is.
• Kies een willekeurige ribbe met graad ten hoogste 15. Ten minste 3/8 van alle ribben voldoet hieraan in een drie-dimensionale oppervlak Delaunay-triangulatie, dus het verwachte aantal steekproeven tot een ribbe met graad ten hoogste 15 is gevonden is 8/3. Beide punten hebben een constante graad en aangezien we zeker weten dat ten minste één van hen graad ten hoogste 7 heeft, kunnen we gebruik maken van een geoptimaliseerd algoritme voor lagegraadspunten in de oppervlak Delaunay-triangulatie.
• Kies een willekeurig punt met graad ten hoogste 7 en gebruik een hashmap van driehoeken als gids. Vergelijkbaar met de ribben, hebben 2/5 van de punten een graad van ten hoogste 7, dus na gemiddeld 5/2 steekproeven hebben we een punt die hieraan voldoet. In de praktijk werken hashmaps vaak erg efficiënt. Door een van de aangrenzende driehoeken op te slaan en deze in een hashmap op te zoeken, kost de plaatsbepaling ook constante tijd. Dit is echter niet zo in het algebraïsche keuzeboommodel. Al deze opties leiden tot algoritmen die plaatsbepaling in O(d) totale verwachte tijd doen en zijn hiermee een logaritmische factor sneller dan voorgaande methoden.
Ster Delaunay-triangulatie
Het tweede aspect waarin we verbeteren ten opzichte van voorgaande methoden is in het reduceren van de structurele complexiteit. Het belang daarvan is zichbaar in het overzicht in figuur 2 . In de Delaunay-triangulatie rechts onderaan zijn de twee witte driehoeken tijdens het constructieproces gecreëeerd, maar deze worden verwijderd zodra de triangulatie wordt samengevoegd met de oude triangulatie tijdens de Sew-stap. Hoewel het er in dit geval slechts twee zijn, kan dit in twee dimensies een aantal lineair in dzijn en in drie dimensies zelfs een kwadratisch aantal, terwijl het aantal nieuwe viervlakken lineair is. We stellen een manier voor om deze driehoeken tijdens het constructieproces al achterwege te laten. In deze samenvatting geven we een versimpelde, intuïtieve beschrijving van onze methode; de volledige methode heeft veel grensgevallen en is in detail beschreven in de scriptie. Om te bepalen welke driehoeken geen onderdeel zijn van de ‘binnenste” driehoeken in figuur 2 , is het belangrijk dat de Delaunay-triangulatie uniek is, en dat een driehoek onderdeel is van de Delaunay-triangulatie als en alleen als de omgeschreven cirkel geen andere punten bevat. Dit betekent dat het toevoegen en het verwijderen van een punt inverse operaties van elkaar zijn (figuur 6) . Het gebied dat verandert bij het verwijderen van punt qis exact hetzelfde als het gebied wat verandert bij het toevoegen van punt q. Hoe helpt dit bij het bepalen van welke driehoeken onderdeel van het binnenste gedeelte zijn? De binnenste driehoeken zijn exact de driehoeken waarbij qin de omgeschreven cirkel ligt. Deze driehoeken zijn zogenaamd in conflict met q, en de driehoeken die bij de Sew-stap weggegooid worden zijn niet in conflict met q. Door tijdens de constructie de driehoeken die niet in conflict zijn met qweg te laten, worden alleen de bruikbare driehoeken opgeslagen. We stellen voor om dit aantal C*(P) te noemen waarvoor geldt: O(d) ≤ O(C*(P)) ≤ O(C(P)) .
 
Figuur 6. Het toevoegen en verwijderen van een punt zijn inverse operaties van elkaar
 
Resultaten
Het doel van mijn scriptie was om niet alleen interessante theoretische resultaten te boeken, maar te zorgen dat deze ook praktisch toepasbaar zijn. Ik heb daarom verschillende varianten van het algoritme geïmplementeerd en dit vergeleken met de implementatie van CGAL, de Computational Geometry Algorithms Library. Alle experimenten zijn voor 3D Delaunay-triangulaties. De looptijd van de verschillende algoritmen is weergegeven in figuur 7 . Het is duidelijk dat onze snelste implementaties een stuk sneller zijn dan die van CGAL. Ook is te zien dat zowel het gebruik van gidspunten (lichtblauw) als het gebruik van de ster Delaunay-triangulatie (oranje) een verbetering geven ten opzichte van CGAL, maar dat de ster Delaunay-triangulatie de grootste winst geeft.
Figuur 7. De looptijd van onze methoden tegenover twee CGAL-implementaties
Het gebruik van een gidspunt hebben we in detail weergegeven in figuur 8 . Hier is duidelijk dat voor lagegraadspunten de kosten voor het bijhouden van de oppervlak Delaunay-triangulatie ervoor zorgen dat er geen winst behaald wordt, maar vanaf een graad van 50 is onze methode een stuk sneller. De structurele complexiteit van de ster Delaunay-triangulatie is duidelijk altijd beter dan de volledige Delaunay-triangulatie. Voor lage graad scheelt het ongeveer 25 procent, zoals te zien is in figuur 9 , maar voor hoge graad scheelt het verschillende orden van grootte (figuur 10) .
Figuur 8. Het gebruik van een gidspunt
 
Figuur 9. De structurele complexiteit per graad voor lage graad
 
Figuur 10. De structurele complexiteit per graad voor hoge graad
 
Uit de experimentele resultaten kan geconcludeerd worden dat naast de theoretische kant het onderzoek ook in praktisch opzicht als geslaagd kan worden beschouwd. Op dit moment verwerk ik de scriptie tot een artikel voor een algoritmiekconferentie samen met mijn begeleider Kevin Buchin, en drie andere auteurs van verschillende instellingen.
 
De scriptie en bijbehorende presentatie zijn beschikbaar op mijn website: www.okke.info
Okke Schrijvers studeerde in 2012 af aan de Technische Universiteit Eindhoven. Inmiddels oriënteert hij zich op een promotieonderzoek aan de prestigieuze Stanford-universiteit in Californië. E-mail: okkeschrijvers@gmail.com
 
 
 
 
 
 

Tag

Onderwerp



Niet gevonden? Vraag het de redactie!

Heeft u het antwoord op uw vraag niet gevonden, of bent u op zoek naar specifieke informatie? Laat het ons weten! Dan zorgen we ervoor dat deze content zo snel mogelijk wordt toegevoegd, of persoonlijk aan u wordt geleverd!

Stel uw vraag