Skip to main content
SpringerLink
Log in

Computational geometry in a curved world

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.

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. Bajaj, C., and Kim, M.-S., Algorithms for planar geometric models,Proceedings of the 15th ICALP, Tampere, Finland, LICS 317, Springer-Verlag, Berlin, 1988.

    Google Scholar 

  2. Chazelle, B., and Dobkin, D., Intersection of convex objects in two and three dimensions,Journal of the Association for Computing Machinery,34, 1987, 1–27. A preliminary version of this paper, entitled “Detection is easier than computation,” appeared in theProceedings of the ACM Symposium on Theory of Computing, Los Angeles, CA, May 1980, pp. 146–153.

    MathSciNet  Google Scholar 

  3. Dobkin, D., and Kirkpatrick, D., Fast detection of polyhedral intersections,Theoretical Computer Science,27, 1983, 241–253.

    Article  MATH  MathSciNet  Google Scholar 

  4. Dobkin, D., and Kirkpatrick, D., A linear algorithm for determining the separation of convex polyhedra,Journal of Algorithms,6, 1985, 381–392.

    Article  MATH  MathSciNet  Google Scholar 

  5. Dobkin, D., and Silver, D., Recipes for geometry and numerical analysis—part I: an empirical study,Proceedings of the ACM Symposium on Computational Geometry, Urbana, IL 1988, pp. 93–105.

  6. Dobkin, D., and Souvaine, D., Computational geometry—a user's guide, inAdvances in Robotics 1: Algorithmic and Geometric Aspects of Robotics (J. T. Schwartz and C. K. Yap, eds.), Erlbaum, Hillsdale, NJ, 1987, pp. 43–93.

    Google Scholar 

  7. Dobkin, D., and Souvaine, D., Detecting and computing the intersection of convex objects, submitted for publication.

  8. Dobkin, D., Souvaine, D., and Van Wyk, C., Decomposition and intersection of simple splinegons,Algorithmica,3, 1988, 473–486.

    Article  MATH  MathSciNet  Google Scholar 

  9. Edelsbrunner, H., Guibas, L. J., and Stolfi, J., Optimal point location in a monotone subdivision, DEC System Research Report, October, 1984.

  10. Forrest, A. R., Invited talk on computational geometry and software engineering, ACM Symposium on Computational Geometry, Yorktown Heights, NY, June, 1986.

  11. Fournier, A., and Montuno, D. Y., Triangulating simple polygons and equivalent problems,ACM Transactions on Graphics,3, 1984, 153–174.

    Article  MATH  Google Scholar 

  12. Graham, R. L., and Yao, F. F., Finding the convex hull of a simple polygon,Journal of Algorithms,4, 1983, 324–331.

    Article  MATH  MathSciNet  Google Scholar 

  13. Hoffman, K., Mehlhorn, K., Rosensthiehl, P., and Tarjan, R., Sorting Jordan sequences in linear time using level-linked search trees,Information and Control,68, 1986, 170–184.

    Article  MathSciNet  Google Scholar 

  14. Hopcroft, J., and Kraft, D., The challenge of robotics, inAdvances in Robotics 1: Algorithmic and Geometry Aspects of Robotics (J. T. Schwartz and C. K. Yap, eds.), Erlbaum, Hillsdale, NJ, 1987, pp. 7–42.

    Google Scholar 

  15. Kim, M., private communication, November 17, 1987.

  16. Kirkpatrick, D., Optimal search in planar subdivisions,SIAM Journal on Computing,12, 1983, 28–35.

    Article  MATH  MathSciNet  Google Scholar 

  17. Knuth, D.,Computers and Typesetting, Vol. C: The METAFONTbook, Addison-Wesley, Reading, MA, 1986.

    Google Scholar 

  18. Lee, D. T., and Preparata, F., An optimal algorithm for finding the kernel of a polygon,Journal of the Association for Computing Machinery,26, 1979, 415–421.

    MATH  MathSciNet  Google Scholar 

  19. Lipton, R., and Tarjan, R., A separator theorem for planar graphs,SIAM Journal of Applied Mathematics,36, 1979, 177–189. A preliminary version of this paper was presented at the Waterloo Conference on Theoretical Computer Science, Waterloo, Ontario, August, 1977.

    Article  MATH  MathSciNet  Google Scholar 

  20. Lipton, R., and Tarjan, R., Applications of a planar separator theorem,Proceedings of the IEEE FOCS Conference, Providence, RI, October 1977, pp. 162–170.

  21. Mehlhorn, K.,Multi-dimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984.

    MATH  Google Scholar 

  22. Pavlidis, T., Curve fitting with conic splines,ACM Transactions on Graphics,2, 1985, 1–31.

    Article  Google Scholar 

  23. Pratt, V., Techniques for conic splines,Computer Graphics,19, 1985, 151–159.

    Article  Google Scholar 

  24. Preparata, F., and Supowit, K., Testing a simple polygon for monotonicity,Information Processing Letters,12, 1981, 161–164.

    Article  MathSciNet  Google Scholar 

  25. Requicha, A., Representations for rigid solids: theory, methods and systems,Computing Surveys,12, 1980, 437–464.

    Article  Google Scholar 

  26. Sarnak, N., and Tarjan, R. E., Planar point location using persistent search trees,Communications of the ACM,29, 1986, 669–679.

    Article  MathSciNet  Google Scholar 

  27. Schäffer, A. A., and Van Wyk, C. J., Convex hulls of piecewise-smooth Jordan curves,Journal of Algorithms,8, 1987, 66–94.

    Article  MATH  MathSciNet  Google Scholar 

  28. Shamos, M., Geometric complexity,Proceedings of the ACM Symposium on Theory of Computing, Albuquerque, NM, May, 1975, pp. 224–233.

  29. Smith, A. R., Invited talk on the complexity of images in the movies, ACM Symposium on Computational Geometry, Yorktown Heights, NY, June, 1986.

  30. Souvaine, D. L., Computational Geometry in a Curved World, Ph.D. Thesis, Princeton University, October, 1986.

  31. Tarjan, R. E., and Van Wyk, C. J., AnO(n log log n)-time algorithm for triangulating simple polygons,SIAM Journal of Computing,17, 1988, 143–178.

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA

    David P. Dobkin

  2. Department of Computer Science, Rutgers University, 08903, New Brunswick, NJ, USA

    Diane L. Souvaine

Authors
  1. David P. Dobkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Diane L. Souvaine
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Bernard Chazelle.

This research was partially supported by National Science Foundation Grants MCS 83-03926, DCR85-05517, and CCR87-00917.

This author's research was also partially supported by an Exxon Foundation Fellowship, by a Henry Rutgers Research Fellowship, and by National Science Foundation Grant CCR88-03549.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dobkin, D.P., Souvaine, D.L. Computational geometry in a curved world. Algorithmica 5, 421–457 (1990). https://doi.org/10.1007/BF01840397

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Key words

Search

Navigation