View planning for mobile robots
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 748-754 vol.2
- https://doi.org/10.1109/robot.1990.126076
Abstract
Two O(N log N) heuristic approaches for planning viewpoints in 2D known environments are described. Both are based on the generalized Delaunay triangulation of a polygon with holes. The main difference between them is the heuristic strategies used to merge the triangles to form the partitioning or covering star polygons. When the environment needs to be explored, an O(N/sup 2/ log N) heuristic scheme which successively selects the viewpoints and views for mobile robots is used. Upper bounds on the number of planned viewpoints and views for each scheme are estimated.Keywords
This publication has 9 references indexed in Scilit:
- Constructing 3-D Models Of A Scene From Planned Multiple ViewsPublished by SPIE-Intl Soc Optical Eng ,1987
- Planning Viewpoints And The Navigation Route Of A Patrol Robot In A Known 2-D EnvironmentPublished by SPIE-Intl Soc Optical Eng ,1987
- An optimal algorithm for constructing the Delaunay triangulation of a set of line segmentsPublished by Association for Computing Machinery (ACM) ,1987
- Constrained Delaunay triangulationsPublished by Association for Computing Machinery (ACM) ,1987
- Worst-case optimal algorithms for constructing visibility polygons with holesPublished by Association for Computing Machinery (ACM) ,1986
- Decomposing a Polygon into Simpler ComponentsSIAM Journal on Computing, 1985
- Computational Geometry and Motion PlanningPublished by Elsevier ,1985
- Some NP-hard polygon decomposition problemsIEEE Transactions on Information Theory, 1983
- An efficient algorithm for decomposing a polygon into star-shaped polygonsPattern Recognition, 1981