Simplified Voronoi Diagrams
The Voronoi diagram has proved to be a useful tool in a variety of contexts in computational geometry. Our interest here is in using the diagram to simplify the planning of collision-free paths for a robot among obstacles, the so-called generalized movers' problem. The Voronoi diagram, as...
| Main Authors: | , |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6471 |
| _version_ | 1826216708450287616 |
|---|---|
| author | Canny, John Donald, Bruce |
| author_facet | Canny, John Donald, Bruce |
| author_sort | Canny, John |
| collection | MIT |
| description | The Voronoi diagram has proved to be a useful tool in a variety of contexts in computational geometry. Our interest here is in using the diagram to simplify the planning of collision-free paths for a robot among obstacles, the so-called generalized movers' problem. The Voronoi diagram, as usually defined, is a strong deformation retract of free space so that free space can be continuously deformed onto the diagram. In particular, any path in free space can be continuously deformed onto the diagram. This means that the diagram is complete for path planning, i.e., searching the original space for paths can be reduced to a search on the diagram. Reducing the dimension of the set to be searched usually reduces the time complexity of the search. Secondly, the diagram leads to robust paths, i.e., paths that are maximally clear of obstacles. |
| first_indexed | 2024-09-23T16:52:09Z |
| id | mit-1721.1/6471 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:52:09Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/64712019-04-12T08:30:56Z Simplified Voronoi Diagrams Canny, John Donald, Bruce The Voronoi diagram has proved to be a useful tool in a variety of contexts in computational geometry. Our interest here is in using the diagram to simplify the planning of collision-free paths for a robot among obstacles, the so-called generalized movers' problem. The Voronoi diagram, as usually defined, is a strong deformation retract of free space so that free space can be continuously deformed onto the diagram. In particular, any path in free space can be continuously deformed onto the diagram. This means that the diagram is complete for path planning, i.e., searching the original space for paths can be reduced to a search on the diagram. Reducing the dimension of the set to be searched usually reduces the time complexity of the search. Secondly, the diagram leads to robust paths, i.e., paths that are maximally clear of obstacles. 2004-10-04T14:57:32Z 2004-10-04T14:57:32Z 1987-04-01 AIM-957 http://hdl.handle.net/1721.1/6471 en_US AIM-957 2139951 bytes 847528 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Canny, John Donald, Bruce Simplified Voronoi Diagrams |
| title | Simplified Voronoi Diagrams |
| title_full | Simplified Voronoi Diagrams |
| title_fullStr | Simplified Voronoi Diagrams |
| title_full_unstemmed | Simplified Voronoi Diagrams |
| title_short | Simplified Voronoi Diagrams |
| title_sort | simplified voronoi diagrams |
| url | http://hdl.handle.net/1721.1/6471 |
| work_keys_str_mv | AT cannyjohn simplifiedvoronoidiagrams AT donaldbruce simplifiedvoronoidiagrams |