Skip to main content
SpringerLink
Log in

A workbench for computational geometry

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. F. Aurenhammer and H. Edelsbrunner, An optimal algorithm for constructing the weighted Voronoi diagram in the plane,Pattern Recognition,17 (1984), 251–275.

    Google Scholar 

  2. C. R. Aragon and R. G. Seidel, Randomized binary search trees,Proc. 30th Symposium on Foundations of Computer Science, pp. 450–455, 1989.

  3. M. D. Atkinson and J.-R. Sack, Uniform generation of combinatorial objects in parallel,J. Parallel Distributed Comput. (1993), to appear.

  4. M. D. Atkinson and J.-R. Sack. Generating binary trees at random,Inform. Process. Lett.,41 (1992), 21–23.

    Google Scholar 

  5. M. D. Atkinson and J.-R. Sack, Uniform Generation of Forests of Restricted Height, Technical Report TR-230, School of Computer Science, Carleton University, 1993.

  6. J. Culberson and G. Rawlins, Turtlegons: generating simple polygons from sequences of angles,Proc. 1st ACM Symposium on Computational Geometry, pp. 305–310, 1985.

  7. L. Devroye, Private communication, McGill University, Novemeber, 1991.

  8. T. Doe and S. Edwards, Course Project: Random Generation of Polygons, Report 95.508, Carleton University, 1984.

  9. L. Devroye, P. Epstein, and J.-R. Sack, On generating random intervals and hyperrect-angles,J. Comput. Graphical Statis.,2(3) (1993), 291–307.

    Google Scholar 

  10. H. Edelsbrunner,Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, Vol. 10 (W. Brauer, G. Rozenberg, and A. Salomaa, eds.), Springer-Verlag, New York, 1987.

    Google Scholar 

  11. P. Epstein, Polygon Shortest Path Algorithms and Applications, 4th year Honours Thesis, Carleton University, May 1990.

  12. P. Epstein, Generation of Random Geometric Objects, M.Sc. thesis, Carleton University, April 1992.

  13. P. Epstein and J.-R. Sack, Generating triangulations at random,Proc. 4th Canadian Conference in Computational Geometry, 1992, pp. 305–310.

  14. A. R. Forrest, Computational geometry and software engineering, towards a geometric computing environment, inTechniques for Computer Graphics (D. F. Rogers and R. A. Earnshaw, eds.), Springer-Verlag, New York, 1987, pp. 23–37.

    Google Scholar 

  15. S. Fortune, A sweepline algorithm for Voronoi diagrams,Algorithmica,2 (1987), 153–174.

    Google Scholar 

  16. A. Fournier and D. Y. Montuno, Triangulating simple polygons and equivalent problems,ACM Trans. Graphics,3 (1984), 153–174.

    Google Scholar 

  17. A. Goldberg and D. Robson,Smalltalk-80: The Language and Its Implementation, Addison-Wesley, Reading, MA, 1983.

    Google Scholar 

  18. L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons,Algorithmica,2(2) (1987), 209–233.

    Google Scholar 

  19. M. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, Triangulating a simple polygon,Inform. Process. Lett.,7(4) (1978), 175–180.

    Google Scholar 

  20. R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set,Inform. Process. Lett,1 (1972), 132–133.

    Google Scholar 

  21. S. Huddieston and K. Mehlhorn, A new data structure for representing sorted lists,Acta Inform.,17 (1982), 157–184.

    Google Scholar 

  22. K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. Tarjan Sorting Jordan sequences in linear time using level-linked search trees,Inform, and Control,68 (1986), 170–184.

    Google Scholar 

  23. R. A. Jarvis, On the identification of the convex hull of a finite set of points in the plane,Inform. Process. Lett.,2 (1973), 18–21.

    Google Scholar 

  24. D. G. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput.,12(1) (1983), 28–35.

    Google Scholar 

  25. A. Knight, A Computational Geometry Workbench and Its Use in Algorithms, M.Sc. thesis, Carleton University, May 1990.

  26. A. Knight and J.-R. Sack, Generating and Sorting Jordan Sequences, Technical Report SCS-TR-188, School of Computer Science, Carleton University, 1991.

  27. A. Knight and J.-R. Sack, Manuscript, Carleton University, 1991.

  28. D. T. Lee, Visibility of a simple polygon,Comput. Vision Graphics Image Process.,22(2) (1983), 207–221.

    Google Scholar 

  29. A. A. Melkman, On-line construction of the convex hull of a simple polygon,Inform. Process. Lett.,25 (1987), 11–12.

    Google Scholar 

  30. K. Mehlhorn and S. Näher: LEDA, a Library of Efficient Data Types and Algorithms, Technical Report A 04/89, FB10, Universität des Saarlandes, Saarbrücken, 1989.

    Google Scholar 

  31. J. O'Rourke, H. Booth, and R. Washington, Connect-the-dots: a new heuristic,Comput. Vision Graphics Image Process.,39(2), (1987), 258–266.

    Google Scholar 

  32. J. O'Rourke and M. Virmani, Generating Random Polygons, Smith Technical Report 11, August 1991.

  33. F. P. Preparata, A new approach to planar point location,SIAM J. Comput.,10(3) (1981), 473–482.

    Google Scholar 

  34. F. P. Preparata and M. I. ShamosComputational Geometry: An Introduction, Texts and Monographs in Computer Science (D. Gries, (ed.), Springer-Verlag, New York, 1985.

    Google Scholar 

  35. J.-R. Sack, Rectilinear Computational Geometry, Ph.D. thesis, McGill University, Montréal, 1984; Technical Report SCS-TR 54, School of Computer Science, Carleton University, 1984.

    Google Scholar 

  36. Peter Schorn, An object oriented workbench for experimental geometric computation,Proc. 2nd Canadian Conference in Computational Geometry, Ottawa, August 6–10, 1990, pp. 172–175.

  37. D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees,J. Assoc. Comput. Mach,32 (1985), 652–686.

    Google Scholar 

  38. S. Suri, Minimum Link Paths in Polygons and Related Problems, Ph.D. thesis, The Johns Hopkins University, 1987.

  39. R. E. Tarjan and C. J. van Wyk, An O(n log log n)-time algorithm for triangulating a simple polygon,SIAM J. Comput.,17(1) (1988), 143–178.

    Google Scholar 

  40. E. Welzl, Constructing the visibility graph ofn line segmens in O(n2) time,Inform. Process. Lett.,20 (1985), 167–171.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ObjecTime Limited, 340 March Road, Suite 200, K2K 2E4, Kanata, Canada

    P. Epstein & J. May

  2. AI Lab, Department of Computer Science, University of Ottawa, K1N 6N5, Ottawa, Canada

    J. Kavanagh

  3. The Object People, 885 Meadowlands Dr., Suite 509, K2C 3N2, Ottawa, Canada

    A. Knight

  4. Advanced Technology Development, Allen Bradley Co., 1201 S Second Street, 53204, Milwaukee, WI, USA

    T. Nguyen

  5. School of Computer Science, Carleton University, 1125 Colonel By Drive, K1S 5B6, Ottawa, Canada

    J. -R. Sack

Authors
  1. P. Epstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Kavanagh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. Knight
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. J. May
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. T. Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. J. -R. Sack
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Kurt Mehlhorn.

This research was partially supported by the Natural Sciences and Engineering Research Council of Canada, Carleton University, and the Univeristy of Passau. Work on this project was carried out in part while A. Knight and J.-R. Sack were at the University of Passau.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Epstein, P., Kavanagh, J., Knight, A. et al. A workbench for computational geometry. Algorithmica 11, 404–428 (1994). https://doi.org/10.1007/BF01187021

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01187021

Key words

Search

Navigation