Abstract
In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensional visibility of the triangles from that vertex. An equivalent statement is that a polygon that is star-shaped with respect to a given vertex can be extended, one triangle at a time, until it includes the entire domain. Arbitrary planar triangulations do not possess this useful property which allows incremental processing of the triangles.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A. V., Hopcroft, J. E., and Ullman, J. D.,Data Structures and Algorithms, Addison-Wesley, Reading, MA, 1983.
De Floriani, L., Falcidieno, B., Pienovi, C., Allen, D., and Nagy, G., A visibility-based model for terrain features,Proceedings of the Second International Symposium on Spatial Data Handling, Seattle, July 1986, pp. 235–250.
Edelsbrunner, H., An acyclicity theorem for cell complexes ind dimensions,Proceedings of the Fifth ACM Symposium on Computational Geometry, Saarbrucken, June 1989, pp. 145–151.
Gold, C., and Cormack, S., Spatially ordered networks and topographic reconstructions,Proceedings of the Second International Symposium on Spatial Data Handling, Seattle, July 1986, pp. 74–85.
Gold, C., and Maydell, U., Triangulation and spatial ordering in computer cartography,Proceedings of the Canadian Cartographic Association Annual Meeting, Vancouver, 1978, pp. 69–81.
Lawson, C. L., Software forC 1 surface interpolation, inMathematical Software III (J. R. Rice, Ed.), Academic Press, New York, 1977, pp. 161–194.
Preparata, F. P., and Shamos, M. I.,Computational Geometry, Springer-Verlag, New York, 1985.
Author information
Authors and Affiliations
Additional information
Communicated by Leonidas J. Guibas.
This work was partially supported by the National Science Foundation's US-Italy Collaborative Research Program under Grant INT-8714578 and Information, Robotics, and Intelligent Research Grant IRI-8704781.
Rights and permissions
About this article
Cite this article
De Floriani, L., Falcidieno, B., Nagy, G. et al. On sorting triangles in a delaunay tessellation. Algorithmica 6, 522–532 (1991). https://doi.org/10.1007/BF01759057
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01759057