Personal tools
You are here: Home Projects Internal Projects The Visibility Voronoi Complex
« June 2017 »
June
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
252627282930
Log in


Forgot your password?
 

The Visibility-Voronoi Complex

LargeOctagonVVc
 Examples of a Visibility-Voronoi
Diagrams
squareVVc

 Abstract

 

We introduce a new type of diagram called the 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 ∞. 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 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 VV(c) -diagram for that c-value.

 

The preprocessing time is O(n2 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 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
 vv(c) with c=0  Vv(c) with c > 0  vv(c) with c = infinity

 C=0

 C>0

 C=inifinity

Links

  • Ron Wein, Jur van den Berg and Dan Halperin
    The Visibility–Voronoi Complex and Its Applications

    Computational Geometry: Theory and Applications, vol. 36(1): 66-87, 2007 [link] [bibtex]
    Preliminary versions appeared in:
    • Proceedings of the 21st ACM Symposium on Computational Geometry (SoCG), pages 63-72, 2005
    • Proceedings of the European Workshop on Computational Geometry (EWCG), pages 151-154, 2005
  • Ron Wein's presentation
    The Visibility–Voronoi Complex and Its Applications

    Presented at the Symposium of Computational Geometry (SoCG), June 2005 [ppt]
  • Ron Wein
    The Integration of Exact Arrangements with Effective Motion Planning
    PhD Thesis, Tel Aviv University, March 2007 [pdf] [bibtex]
  • Jur van den Berg
    Path Planning in Dynamic Environments.
    PhD Thesis, Utrecht University, The Netherlands, 2007

Contact

Ron Wein
http://www.cs.tau.ac.il/~eitanyaf eitan.yaffe@gmail.com
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Document Actions