Geometric Data Structures and Their Selected Applications
Finding the shortest path between two positions is a
fundamental problem in transportation, routing, and communications
applications. In robot motion planning, the robot should pass around
the obstacles touching none of them, i.e. the goal is to find a
collision-free path from a starting to a target position. This task has
many specific formulations depending on the shape of obstacles,
allowable directions of movements, knowledge of the scene, etc.
Research of path planning has yielded many fundamentally different
approaches to its solution, mainly based on various decomposition
and roadmap methods. In this paper, we show a possible use of
visibility graphs in point-to-point motion planning in the Euclidean
plane and an alternative approach using Voronoi diagrams that
decreases the probability of collisions with obstacles. The second
application area, investigated here, is focused on problems of finding
minimal networks connecting a set of given points in the plane using
either only straight connections between pairs of points (minimum
spanning tree) or allowing the addition of auxiliary points to the set
to obtain shorter spanning networks (minimum Steiner tree).
[1] D.-Z. Du, J.M. Smith, and J.H. Rubinstein, Advances in Steiner Trees.
Dordrecht: Kluwer Academic Publishers, 2000.
[2] S.M. LaValle, Planning Algorithms. Cambridge: University Press, 2006.
[3] F. Aurenhammer, "Voronoi Diagrams - A Survey of a Fundamental
Geometric Data Structure," ACM Computing Surveys, vol. 23, no. 3, pp.
345-405, 1991.
[4] M. de Berg, M., M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry: Algorithms and Applications. Berlin:
Springer-Verlag, 2000.
[5] D.A. Du and F.K. Hwang (eds.), Euclidean Geometry and Computers.
Singapore: World Scientific Publishing ,1992.
[6] A.O. Ivanov and A.A. Tuzhilin, Minimal Networks. The Steiner Tree
Problem and its Generalizations. Boca Raton: CRC Press, 1994.
[7] A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations
and Applications of Voronoi Diagrams. New York: John Wiley & Sons,
2000.
[8] S. Guha and I. Suzuki, "Proximity Problems for Points on a Rectilinear
Plane with Rectangular Obstacles," Algorithmica, vol. 17, pp. 281-307,
1997.
[9] M. Šeda, "Rectilinear Voronoi Diagram-Based Motion Planning in the
Plane with Obstacles," Elektronika (Poland), no. 8-9, pp. 24-26, 2004.
[10] D.M. Mount, ÔÇ×Design and Analysis of Computer Algorithms," Lecture
Notes, University of Maryland, College Park, 1999, 131 pp.
[11] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem.
Amsterdam: North-Holland, 1992.
[12] D. Cheriton and R.E. Tarjan, "Finding Minimum Spanning Trees," SIAM
Journal on Computing, vol. 5, no. 4, pp. 724-742, 1976.
[13] D.-Z. Du and F.K. Hwang, "A Proof of the Gilbert-Pollak Conjecture on
the Steiner Ratio," Algorithmica, vol. 7, pp. 121-135, 1992.
[14] D.R. Dreyer and M.L. Overton, "Two Heuristics for Euclidean Steiner
Tree Problem," Journal on Global Optimization, vol. 13, pp. 95-106,
1998.
[15] M. Šeda, "Solving the Euclidean Steiner Tree Problem Using Delaunay
Triangulation," WSEAS Transactions on Computers, vol. 4, no. 6, pp.
471-476, 2005.
[16] M.I. Shamos and D. Hoey, "Closest Point Problems," in Proc. 16th
Annual Symposium on Foundations of Computer Science FOCS '75,
Berkeley, 1975, pp. 151-162.
[1] D.-Z. Du, J.M. Smith, and J.H. Rubinstein, Advances in Steiner Trees.
Dordrecht: Kluwer Academic Publishers, 2000.
[2] S.M. LaValle, Planning Algorithms. Cambridge: University Press, 2006.
[3] F. Aurenhammer, "Voronoi Diagrams - A Survey of a Fundamental
Geometric Data Structure," ACM Computing Surveys, vol. 23, no. 3, pp.
345-405, 1991.
[4] M. de Berg, M., M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry: Algorithms and Applications. Berlin:
Springer-Verlag, 2000.
[5] D.A. Du and F.K. Hwang (eds.), Euclidean Geometry and Computers.
Singapore: World Scientific Publishing ,1992.
[6] A.O. Ivanov and A.A. Tuzhilin, Minimal Networks. The Steiner Tree
Problem and its Generalizations. Boca Raton: CRC Press, 1994.
[7] A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations
and Applications of Voronoi Diagrams. New York: John Wiley & Sons,
2000.
[8] S. Guha and I. Suzuki, "Proximity Problems for Points on a Rectilinear
Plane with Rectangular Obstacles," Algorithmica, vol. 17, pp. 281-307,
1997.
[9] M. Šeda, "Rectilinear Voronoi Diagram-Based Motion Planning in the
Plane with Obstacles," Elektronika (Poland), no. 8-9, pp. 24-26, 2004.
[10] D.M. Mount, ÔÇ×Design and Analysis of Computer Algorithms," Lecture
Notes, University of Maryland, College Park, 1999, 131 pp.
[11] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem.
Amsterdam: North-Holland, 1992.
[12] D. Cheriton and R.E. Tarjan, "Finding Minimum Spanning Trees," SIAM
Journal on Computing, vol. 5, no. 4, pp. 724-742, 1976.
[13] D.-Z. Du and F.K. Hwang, "A Proof of the Gilbert-Pollak Conjecture on
the Steiner Ratio," Algorithmica, vol. 7, pp. 121-135, 1992.
[14] D.R. Dreyer and M.L. Overton, "Two Heuristics for Euclidean Steiner
Tree Problem," Journal on Global Optimization, vol. 13, pp. 95-106,
1998.
[15] M. Šeda, "Solving the Euclidean Steiner Tree Problem Using Delaunay
Triangulation," WSEAS Transactions on Computers, vol. 4, no. 6, pp.
471-476, 2005.
[16] M.I. Shamos and D. Hoey, "Closest Point Problems," in Proc. 16th
Annual Symposium on Foundations of Computer Science FOCS '75,
Berkeley, 1975, pp. 151-162.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:58031", author = "Miloš Šeda", title = "Geometric Data Structures and Their Selected Applications", abstract = "Finding the shortest path between two positions is a
fundamental problem in transportation, routing, and communications
applications. In robot motion planning, the robot should pass around
the obstacles touching none of them, i.e. the goal is to find a
collision-free path from a starting to a target position. This task has
many specific formulations depending on the shape of obstacles,
allowable directions of movements, knowledge of the scene, etc.
Research of path planning has yielded many fundamentally different
approaches to its solution, mainly based on various decomposition
and roadmap methods. In this paper, we show a possible use of
visibility graphs in point-to-point motion planning in the Euclidean
plane and an alternative approach using Voronoi diagrams that
decreases the probability of collisions with obstacles. The second
application area, investigated here, is focused on problems of finding
minimal networks connecting a set of given points in the plane using
either only straight connections between pairs of points (minimum
spanning tree) or allowing the addition of auxiliary points to the set
to obtain shorter spanning networks (minimum Steiner tree).", keywords = "motion planning, spanning tree, Steiner tree,
Delaunay triangulation, Voronoi diagram.", volume = "1", number = "11", pages = "546-6", }