LIPIcs.SoCG.2017.31.pdf
- Filesize: 0.72 MB
- 15 pages
Document
High Dimensional Consistent Digital Segments
Authors
-
Part of:
Volume:
33rd International Symposium on Computational Geometry (SoCG 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-06-20
Cite As Get BibTex
Man-Kwun Chiu and Matias Korman. High Dimensional Consistent Digital Segments. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.31
Abstract
We consider the problem of digitalizing Euclidean line segments from R^d to Z^d. Christ {et al.} (DCG, 2012) showed how to construct a set of {consistent digital segments} (CDS) for d=2: a collection of segments connecting any two points in Z^2 that satisfies the natural extension of the Euclidean axioms to Z^d. In this paper we study the construction of CDSs in higher dimensions.
We show that any total order can be used to create a set of {consistent digital rays} CDR in Z^d (a set of rays emanating from a fixed point p that satisfies the extension of the Euclidean axioms). We fully characterize for which total orders the construction holds and study their Hausdorff distance, which in particular positively answers the question posed by Christ {et al.}.
Subject Classification
Keywords
- Consistent Digital Line Segments
- Digital Geometry
- Computer Vision
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Iffat Chowdhury and Matt Gibson. A characterization of consistent digital line segments in ℤ². In Proceedings of the 23rd Annual European Symposium on Algorithms, pages 337-348, 2015.
-
Iffat Chowdhury and Matt Gibson. Constructing consistent digital line segments. In Proceedings of the 12th Latin American Theoretical Informatics Symposium, pages 263-274, 2016.
-
Tobias Christ, Dömötör Pálvölgyi, and Miloš Stojaković. Consistent digital line segments. Discrete & Computational Geometry, 47(4):691-710, 2012.
-
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama. Consistent digital rays. Discrete and Computational Geometry, 42(3):359-378, 2009.
-
Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, and Paul J. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proceedings of the 13th Annual Symposium on Computational Geometry, pages 284-293, 1997.
-
Daniel H. Greene and F. Frances Yao. Finite-resolution computational geometry. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 143-152, 1986.
-
M. G. Luby. Grid geometries which preserve properties of Euclidean geometry: A study of graphics line drawing algorithms. In NATO Conference on Graphics/CAD, pages 397-432, 1987.
-
Kokichi Sugihara. Robust geometric computation based on topological consistency. In Proceedings of the 9th International Conference on Computational Science, pages 12-26, 2001.
-
Johannes van der Corput. Verteilungsfunktionen I &II (in german). Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen, 38:813-820, 1058-1066, 1935.