Skip to main content
padlock icon - secure page this page is secure

A framework of Voronoi diagram for planning multiple paths in free space

Buy Article:

$60.00 + tax (Refund Policy)

Most of the emphasis in path planning, a topic of much interest in several domains, has been on finding the optimal path or at most k optimal paths. However, in domains such as adversarial planning, one of the agents might deliberately take less optimal paths to confuse the opponent, and by the same token an agent, for inferring opponent's intent, has to consider all possible paths that the opponent might take. We introduce the notion of representative paths in free space (2D) and study the problem of computing all representative paths with different properties, such as all representative paths with at most L loops, among polygonal regions using a framework of Voronoi diagram. We prove three properties: (1) the upper and lower bounds to the number of simple paths in a Voronoi graph (2) given any path, a homotopic path can always be obtained from the Voronoi diagram of the regions and (3) all representative paths with a given property might not be always obtainable from the Voronoi graph even after searching the graph exhaustively and present an algorithm to work around this limitation. We also show how our findings can be applied for efficient entity re-identification, a problem involving a large number of dynamic entities and obstacles in the military domain.
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Article Media
No Metrics

Keywords: Voronoi diagram; entity re-identification; enumerate all paths; free space; homotopy; number of paths; representative path

Document Type: Research Article

Affiliations: 1: Department of Electrical & Computer Engineering, Institute for Intelligent Systems, University of Memphis, Memphis, TN, USA, 2: Department of Computer Science & Engineering, Ohio State University, Columbus, OH, USA,

Publication date: December 1, 2013

More about this publication?
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more