A Case Study on the Cost of Geometric Computing

1. S. G. Akl. Two remarks on a convex hull algorithm. Inform. Process. Lett., 8(2):108–109, 1979.

   Article  MATH  MathSciNet  Google Scholar 

2. S. G. Akl. Corrigendum on convex hull algorithms. Inform. Process. Lett., 10(3):168, 1980.

   Article  MathSciNet  Google Scholar 

3. S. G. Akl and G. T. Toussaint. A fast convex hull algorithm. Inform. Process. Lett., 7(5):219–222, 1978.

   Article  MATH  MathSciNet  Google Scholar 

4. G. Alefeld and J. Herzberger. Introduction to Interval Computation. Academic Press, New York, 1983.

   Google Scholar 

5. D. C. S. Allison and M. T. Noga. Some performance tests of convex hull algorithms. BIT, 24:2–13, 1984.

   Article  MATH  MathSciNet  Google Scholar 

6. K. R. Anderson. A reevaluation of an efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 7(1):53–55, 1978.

   Article  MATH  MathSciNet  Google Scholar 

7. A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Inform. Process. Lett., 9(5):216–219, 1979.

   Article  MATH  Google Scholar 

8. B. K. Bhattacharya and G. T. Toussaint. Time-and storage-efficient implementation of an optimal convex hull algorithm. Image Vision Comput., 1:140–144, 1983.

   Article  Google Scholar 

9. J.-D. Boissonnat and F. Preparata. Robust plane sweep for intersecting segments. Technical Report 3270, INRIA, Sophia-Antipolis, France, September 1997.

   Google Scholar 

10. K. Briggs. The doubledouble home page. http://epidem13.plantsci.cam.ac.uk/~kbriggs/doubledouble.html.

11. H. Brönnimann, C. Burnikel, and S. Pion. Interval arithmetic yields efficient dynamic filters for computational geometry. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 165–174, 1998.

    Google Scholar 

12. C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra. A strong and easily computable separation bound for arithmetic expressions involving square roots. In Proc. of the 8th ACM-SIAM Symp. on Discrete Algorithms, pages 702–709, 1997.

    Google Scholar 

13. C. Burnikel, J. Könemann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig. Exact geometric computation in LEDA. In Proceedings of the 11th ACM Symposium on Computational Geometry, pages C18–C19, 1995.

    Google Scholar 

14. C. Burnikel, K. Mehlhorn, and S. Schirra. The LEDA class real number. Technical Report MPI-I-96-1-001, Max-Planck-Institut für Informatik, 1996.

    Google Scholar 

15. A. Bykat. Convex hull of a finite set of points in two dimensions. Inform. Process. Lett., 7:296–298, 1978.

    Article  MATH  MathSciNet  Google Scholar 

16. CGAL project. http://www.cs.uu.nl/CGAL

17. T. M. Y. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 10–19, 1995.

    Google Scholar 

18. K. Clarkson. A short, complete planar convex hull code. http://cm.bell-labs.com/who/clarkson/2dch.c.

19. T. J. Dekker. A floating-point technique for extending the available precision. Numerische Mathematik, 18:224–242, 1971.

    Article  MATH  MathSciNet  Google Scholar 

20. F. Dévai and T. Szendrényi. Comments on convex hull of a finite set of points in two dimensions. Inform. Process. Lett., 9:141–142, 1979.

    Article  MATH  Google Scholar 

21. W. F. Eddy. A new convex hull algorithm for planar sets. ACM Trans. Math. Softw., 3:398–403 and 411–412, 1977.

    Article  MATH  Google Scholar 

22. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer Verlag, 1986.

    Google Scholar 

23. S. Fortune and C. Van Wyk. Static analysis yields efficient exact integer arithmetic for computational geometry. ACM Transactions on Graphics, 15(3):223–248, 1996.

    Article  Google Scholar 

24. A. Fournier. Comments on convex hull of a finite set of points in two dimensions. Inform. Process. Lett., 8:173, 1979.

    Article  MathSciNet  Google Scholar 

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

    Article  MATH  Google Scholar 

26. T. Granlund. GNU MP, The GNU Multiple Precision Arithmetic Library, 2.0.2 edition, June 1996.

    Google Scholar 

27. P. J. Green and B. W. Silverman. Constructing the convex hull of a set of points in the plane. Comput. J., 22:262–266, 1979.

    Article  MATH  Google Scholar 

28. C. C. Handley. Efficient planar convex hull algorithm. Image Vision Comput., 3:29–35, 1985.

    Article  Google Scholar 

29. S. Hertel. An almost trivial convex hull algorithm for a presorted point set in the plane. Report A83/08, Fachber. Inform., Univ. Saarlandes, Saarbrücken, West Germany, 1983.

    Google Scholar 

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

    Article  MATH  Google Scholar 

31. M. Karasick, D. Lieber, and L.R. Nackman. Efficient Delaunay triangulation using rational arithmetic. ACM Transactions on Graphics, 10(1):71–91, 1991.

    Article  Google Scholar 

32. D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? SIAM J. Comput., 15:287–299, 1986.

    Article  MATH  MathSciNet  Google Scholar 

33. J. Koplowitz and D. Jouppi. A more efficient convex hull algorithm. Inform. Process. Lett., 7:56–57, 1978.

    Article  MATH  MathSciNet  Google Scholar 

34. G. Liotta, F. P. Preparata, and R. Tamassia. Robust proximity queries: an illustration of degree-driven algorithm design. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 156–165, 1997.

    Google Scholar 

35. S. B. Lippman and J. Lajoie. C++ primer. Addison-Wesley, Reading, MA, 3rd ed., 1998.

    Google Scholar 

36. M. M. McQueen and G. T. Toussaint. On the ultimate convex hull algorithm in practice. Pattern Recogn. Lett., 3:29–34, 1985.

    Article  Google Scholar 

37. K. Mehlhorn. Multi-dimensional Searching and Computational Geometry, volume 3 of Data Structures and Algorithms. Springer-Verlag, Heidelberg, Germany, 1984.

    MATH  Google Scholar 

38. K. Mehlhorn and S. Näher. LEDA, a platform for combinatorial and geometric computing. Communications of the ACM, 38:96–102, 1995.

    Article  Google Scholar 

39. K. Mehlhorn, S. Näher, M. Seel, and C. Uhrig. The LEDA User manual, 3.7 edition, 1998. see http://www.mpi-sb.mpg.de/LEDA/leda.html.

40. R. E. Moore. Methods and Applications of Interval Analysis. SIAM, Philadelphia, 1979.

    MATH  Google Scholar 

41. M. H. Overmars and J. van Leeuwen. Further comments on Bykat’s convex hull algorithm. Inform. Process. Lett., 10:209–212, 1980.

    Article  MATH  MathSciNet  Google Scholar 

42. D. M. Priest. On Properties of Floating-Point Arithmetic: Numerical Stability and the Cost of Accurate Computations. PhD thesis, Department of Mathematics, University of California at Berkeley, 1992.

    Google Scholar 

43. J. R. Shewchuk. C code for the 2d and 3d orientation and incircle tests, and for arbitrary precision floating-point addition and multiplication. Available from http://www.cs.cmu.edu/~quake/robust.html.

44. J. R. Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Technical Report CMU-CS-96-140, School of Computer Science, Carnegie Mellon University, 1996.

    Google Scholar 

45. G. T. Toussaint. A historical note on convex hull finding algorithms. Pattern Recogn. Lett., 3:21–28, 1985.

    Article  Google Scholar 

Download references