Simplified Voronoi Diagrams

dc.creator	Canny, John
dc.creator	Donald, Bruce
dc.date	2004-10-04T14:57:32Z
dc.date	2004-10-04T14:57:32Z
dc.date	1987-04-01
dc.date.accessioned	2013-10-09T02:45:36Z
dc.date.available	2013-10-09T02:45:36Z
dc.date.issued	2013-10-09
dc.identifier	AIM-957
dc.identifier	http://hdl.handle.net/1721.1/6471
dc.identifier.uri	http://koha.mediu.edu.my:8181/xmlui/handle/1721
dc.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.
dc.format	2139951 bytes
dc.format	847528 bytes
dc.format	application/postscript
dc.format	application/pdf
dc.language	en_US
dc.relation	AIM-957
dc.title	Simplified Voronoi Diagrams

Files in this item

Files	Size	Format	View
There are no files associated with this item.