Dynamic Voronoi Diagram for Moving Disks
- Title
- Dynamic Voronoi Diagram for Moving Disks
- Author
- 김덕수
- Keywords
- unmanned vehicles; moving vehicles; path planning; collision avoidance; topology event; weighted Voronoi diagram
- Issue Date
- 2019-12
- Publisher
- IEEE COMPUTER SOC
- Citation
- IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, page. 1-18
- Abstract
- Voronoi diagrams are powerful for understanding spatial properties. However, few reports have been made for moving generators despite their important applications. We present a topology-oriented event-increment (TOI-E) algorithm for constructing a Voronoi diagram of moving circular disks in the plane over the time horizon [ 0,t∞ ). The proposed TOI-E algorithm computes the event history of the Voronoi diagram over the entire time horizon in O(kFlogn+kCnlogn) time with O(nlogn) preprocessing time and O(n+kF+kC) memory for n disk generators, kF edge flips, and kC disk collisions during the time horizon. Given an event history, the Voronoi diagram of an arbitrary moment t∗<t∞ can be constructed in O(k∗+n) time where k∗ represents the number of events in [0,t∗) . An example of the collision avoidance problem among moving disks is given by predicting future conjunctions among the disks using the proposed algorithm. Dynamic Voronoi diagrams will be very useful as a platform for the planning and management of the traffics of unmanned vehicles such as cars on street, vessels on surface, drones and airplanes in air, and satellites in geospace.
- URI
- https://ieeexplore.ieee.org/document/8933488https://repository.hanyang.ac.kr/handle/20.500.11754/156630
- ISSN
- 1077-2626; 1941-0506
- DOI
- 10.1109/TVCG.2019.2959321
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > MECHANICAL ENGINEERING(기계공학부) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML