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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bajaj, C., and Kim, M.-S., Algorithms for planar geometric models,Proceedings of the 15th ICALP, Tampere, Finland, LICS 317, Springer-Verlag, Berlin, 1988.
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.
Dobkin, D., and Kirkpatrick, D., Fast detection of polyhedral intersections,Theoretical Computer Science,27, 1983, 241–253.
Dobkin, D., and Kirkpatrick, D., A linear algorithm for determining the separation of convex polyhedra,Journal of Algorithms,6, 1985, 381–392.
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.
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.
Dobkin, D., and Souvaine, D., Detecting and computing the intersection of convex objects, submitted for publication.
Dobkin, D., Souvaine, D., and Van Wyk, C., Decomposition and intersection of simple splinegons,Algorithmica,3, 1988, 473–486.
Edelsbrunner, H., Guibas, L. J., and Stolfi, J., Optimal point location in a monotone subdivision, DEC System Research Report, October, 1984.
Forrest, A. R., Invited talk on computational geometry and software engineering, ACM Symposium on Computational Geometry, Yorktown Heights, NY, June, 1986.
Fournier, A., and Montuno, D. Y., Triangulating simple polygons and equivalent problems,ACM Transactions on Graphics,3, 1984, 153–174.
Graham, R. L., and Yao, F. F., Finding the convex hull of a simple polygon,Journal of Algorithms,4, 1983, 324–331.
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.
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.
Kim, M., private communication, November 17, 1987.
Kirkpatrick, D., Optimal search in planar subdivisions,SIAM Journal on Computing,12, 1983, 28–35.
Knuth, D.,Computers and Typesetting, Vol. C: The METAFONTbook, Addison-Wesley, Reading, MA, 1986.
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.
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.
Lipton, R., and Tarjan, R., Applications of a planar separator theorem,Proceedings of the IEEE FOCS Conference, Providence, RI, October 1977, pp. 162–170.
Mehlhorn, K.,Multi-dimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984.
Pavlidis, T., Curve fitting with conic splines,ACM Transactions on Graphics,2, 1985, 1–31.
Pratt, V., Techniques for conic splines,Computer Graphics,19, 1985, 151–159.
Preparata, F., and Supowit, K., Testing a simple polygon for monotonicity,Information Processing Letters,12, 1981, 161–164.
Requicha, A., Representations for rigid solids: theory, methods and systems,Computing Surveys,12, 1980, 437–464.
Sarnak, N., and Tarjan, R. E., Planar point location using persistent search trees,Communications of the ACM,29, 1986, 669–679.
Schäffer, A. A., and Van Wyk, C. J., Convex hulls of piecewise-smooth Jordan curves,Journal of Algorithms,8, 1987, 66–94.
Shamos, M., Geometric complexity,Proceedings of the ACM Symposium on Theory of Computing, Albuquerque, NM, May, 1975, pp. 224–233.
Smith, A. R., Invited talk on the complexity of images in the movies, ACM Symposium on Computational Geometry, Yorktown Heights, NY, June, 1986.
Souvaine, D. L., Computational Geometry in a Curved World, Ph.D. Thesis, Princeton University, October, 1986.
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.
Author information
Authors and Affiliations
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
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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01840397