Vi introducerar en ny typ av diagram som kallas VV (c) -diagram (Visibility-Voronoi diagram för clearance c), som är en hybrid mellan synlighetsgrafen och Voronoi diagram av polygoner i planet. Den utvecklas från synlighetsgrafen till Voronoi-diagrammet när parametern c växer från 0 till ∞. Detta diagram kan användas för att planera naturliga vägar för en robot översätta mitt polygonala hinder i planet. En naturlig väg är kort, smidig, och håller - där det är möjligt - en mängd avstånd c från hindren. VV (c) -diagram innehåller sådana vägar. Vi föreslår också en algoritm som är kapabel att förbehandla en scen av konfiguration-rymd polygonala hinder och konstruerar en datastruktur som kallas VV-komplexet. VVcomplex kan användas för att effektivt planera rörelsevägar för alla start- och målkonfigurationer och valfritt clearancevärde c, utan att uttryckligen behöva konstruera VV (c) -diagram för detta c-värde. Förbehandlingstiden är O(n 2 log n), där n är det totala antalet hinder hörn, och datastrukturen kan frågas direkt för alla c-värde genom att bara utföra en Dijkstra sökning. Vi har implementerat ett Cgal-baserat programvarupaket för beräkning av VV (c) -diagram på ett exakt sätt för ett givet clearancevärde, och använt det för att planera naturliga vägar i olika applikationer.
Wein m.fl. REF visar hur man konstruerar en sikt Voronoi-komplex i O(n 2 log n) tid.
The visibility--voronoi complex and its applications
{'venue': "SCG '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}