AN ART GALLERY-BASED APPROACH: ROADMAP CONSTRUCTION AND PATH PLANNING IN GLOBAL ENVIRONMENTS

L. Lulu and A. Elnagar

References

  1. [1] R. Honsberger, Mathematical gems II (Washington, USA: Mathematical association of America, 1976), 104–110.
  2. [2] V. Chvatal, A combinatorial theorem in plane geometry, Combinatorial Theory Series B, 18, 1975, 39–41. doi:10.1016/0095-8956(75)90061-1
  3. [3] J. O’Rourke, Art gallery theorems and algorithms (Oxford: Oxford University Press, 1987).
  4. [4] J. Urrutia, Art gallery and illumination problems (chapter 22), In J. R. Sack & J. Urrutia (Eds.), Handbook of computational geometry (North Holland, Amsterdam: Elsevier Science, 2000), 973–1026.
  5. [5] D. Haussler & E. Welzl, Recent results on illumination problems, Discrete Computational Geometry, 2, 1987, 27–151.
  6. [6] A. Laurentini, Guarding the walls of an art gallery, The Visual Computer Journal, 15(6), 1999, 265–278. doi:10.1007/s003710050177
  7. [7] M. de Berg, M. van Kreveld, M. Overmars, & O. Schwarzkoph, Computational geometry: algorithms and applications (Berlin: Springer-Verlag, 2000).
  8. [8] S. Fisk, A short proof of Chvatals watchman theorem, Journal of Combinatorial Theory Series B, 24, 1978, 374. doi:10.1016/0095-8956(78)90059-X
  9. [9] I. Bjorling-Sachs & D. Souvaine, An efficient algorithm for guard placement in polygons with holes, Discrete and Computational Geometry, 13(1), 1995, 77–109. doi:10.1007/BF02574029
  10. [10] F. Hoffmann, M. Kaufmann, & K. Kriegel, The art gallery theorem for polygons with holes. Proc. Symp. of Foundations of Computer Science, San Juan, Puerto Rico, 1991, 39–48.
  11. [11] L. Lulu, An art gallery-based approach to autonomous robot motion planning in global environments, Master’s thesis, University of Sharjah, Sharjah, UAE, 2004.
  12. [12] L. Lulu & A. Elnagar, Performance evaluation of robot motion planning algorithms: Vis-prm vs. agrm, Proc. Int. IEEE Conf. on Systems, Man and Cybernetics, The Hague, The Netherlands, 2004, 496–501.
  13. [13] T. Lozano-Pérez, Spatial planning: a configuration space approach, IEEE Transactions on Computers, 2, 1983, 108–120. doi:10.1109/TC.1983.1676196
  14. [14] M. Garey, D. Johonson, F. Preparat, & R. Tarjan, Triangulating a simple polygon. Informat Processing Letters, 7, 1978, 175–179. doi:10.1016/0020-0190(78)90062-5
  15. [15] L. Kavraki, P. Svestka, J.-C. Latombe, & M. Overmars, Probabilistic roadmaps for path planning in high dimensional configuration spaces, IEEE Journal of Robotics and Automation, 12, 1996, 566–580. doi:10.1109/70.508439
  16. [16] R. Tarjan & J. van Leeuwen, Worst-case analysis of set union algorithms, Journal of the ACM, 31, 1984, 245–281. doi:10.1145/62.2160
  17. [17] E. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, 1, 1959, 269–271. doi:10.1007/BF01386390
  18. [18] T. Cormen, C. Leiserson, R. Rivest, & C. Stein, Introduction to algorithms (Boston: McGraw-Hill Book Company, 2001).
  19. [19] D. Lee & F. Preparata, Location of a point in a planar subdivision and its applications, SIAM Journal of Computing, 6, 1977, 594–606. doi:10.1137/0206043
  20. [20] R. Tarjan, Efficiency of a good but not linear set union algorithm, Journal of the ACM, 22, 1975, 215–225. doi:10.1145/321879.321884

Important Links:

Go Back