The Visibility-Voronoi Complex

Abstract

The Visibility-Voronoi Complex
Examples of a Visibility-Voronoi Diagrams

We introduce a new type of diagram called the \(\text{VV}(c)\)-diagram (the Visibility–Voronoi diagram for clearance \(c\)), which is a hybrid between the visibility graph and the Voronoi diagram of polygons in the plane. It evolves from the visibility graph to the Voronoi diagram as the parameter c grows from 0 to \(\infty\). This diagram can be used for planning natural-looking paths for a robot translating amidst polygonal obstacles in the plane. A natural-looking path is short, smooth, and keeps—where possible—an amount of clearance \(c\) from the obstacles. The \(\text{VV}(c)\)-diagram contains such paths.

We also propose an algorithm that is capable of preprocessing a scene of configuration-space polygonal obstacles and constructs a data structure called the VV-complex. The VV-complex can be used to efficiently plan motion paths for any start and goal configuration and any clearance value \(c\), without having to explicitly construct the \(\text{VV}(c)\)-diagram for that \(c\)-value.

The Visibility-Voronoi Complex

The preprocessing time is \(O(n^2 \log n)\), where \(n\) is the total number of obstacle vertices, and the data structure can be queried directly for any c-value by merely performing a Dijkstra search. We have implemented a CGAL-based software package for computing the \(\text{VV}(c)\)-diagram in an exact manner for a given clearance value, and used it to plan natural-looking paths in various applications.

Illustration
Visibility-Voronoi Diagrams with different clearance values

C=0
C=0

C>0
C>0

C=inifinity
C=∞

Links

  • Ron Wein, Jur van den Berg and Dan Halperin
    The Visibility-Voronoi Complex and Its Applications
    Computational Geometry: Theory and Applications, 36(1): 66–87, 2007 [link][bibtex]
    Preliminary versions appeared in:

    • In Proceedings of the 21st ACM Symposium on Computational Geometry (SoCG), pages 63–72, 2005 [link][bibtex]
    • In Proceedings of the 21st European Workshop on Computational Geometry (EuroCG), pages 151–154, 2005 [link][bibtex]
  • Ron Wein
    The Integration of Exact Arrangements with Effective Motion Planning
    Ph.D. Thesis, Tel Aviv University, March 2007 [pdf][bibtex]
  • Jur van den Berg
    Path Planning in Dynamic Environments.
    Ph.D. Thesis, Utrecht University, The Netherlands, 2007

Contacts

Ron Wein
Dan Halperin 
@inproceedings{,
  author       = {Ron Wein and Jur van den Berg and Dan Halperin},
  title        = {The visibility-Voronoi complex and its applications},
  booktitle    = {Proceedings of the 21st European Workshop on Computational Geometry ({EuroCG})},
  pages        = {151--154},
  year         = {2005},
  site         = {Eindhoven, Netherlands}
}

@phdthesis{w-ieaem-07,
  author      = {Ron Wein},
  title       = {The Integration of Exact Arrangements with Effective Motion Planning},
  type        = {{P}h.{D}. Thesis},
  school      = {The Blavatnik School of Computer Science, Tel-Aviv University},
  year        = {2007}
}

@inproceedings{wvh-vvcia-05,
  author = {Ron Wein and Jur van den Berg and Dan Halperin},
  title = {The visibility--voronoi complex and its applications},
  booktitle = {Proceedings of the 21st {ACM} Symposium on Computational Geometry ({SoCG})},
  year = {2005},
  pages = {63--72},
  doi = {10.1145/1064092.1064104}
}

@article{wvh-vvcia-07,
  author = {Ron Wein, Jur van den Berg and Dan Halperin},
  title = {The visibility-Voronoi complex and its applications},
  journal = {Computational Geometry: Theory and Applications},
  volume = {6},
  number = {1},
  year = {2007},
  pages = {66--78},
  doi = {10.1016/j.comgeo.2005.11.007}
}

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content