LIPIcs.ESA.2020.34.pdf
- Filesize: 0.88 MB
- 22 pages
Document
Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays
Authors
Man-Kwun Chiu 
,
Martin Suderland ,
-
Part of:
Volume:
28th Annual European Symposium on Algorithms (ESA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-26
File
Document Identifiers
Author Details
Acknowledgements
The authors would like to thank Matthew Gibson, Evanthia Papadopoulou, André van Renssen and Marcel Roeloffzen for their helpful discussions during the creation of this paper. The authors would also like to thank the anonymous reviewers for the many comments that helped improve the paper. We would especially like to thank the SODA reviewer that showed us how to improve the lower bound from Ω(log^{1/d} N) to Ω(log^{1/(d-1)}N).
Cite As Get BibTex
Man-Kwun Chiu, Matias Korman, Martin Suderland, and Takeshi Tokuyama. Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 34:1-34:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.34
Abstract
We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in ℤ^d. The construction must be consistent (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with Θ(log N) error, where resemblance between segments is measured with the Hausdorff distance, and N is the L₁ distance between the two points. This construction was considered tight because of a Ω(log N) lower bound that applies to any consistent construction in ℤ².
In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in d dimensions must have Ω(log^{1/(d-1)} N) error. We tie the error of a consistent construction in high dimensions to the error of similar weak constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with o(log N) error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. In order to show our lower bound, we also consider a colored variation of the concept of discrepancy of a set of points that we find of independent interest.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Consistent Digital Line Segments
- Digital Geometry
- Discrepancy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Tetsuo Asano, Danny Z. Chen, Naoki Katoh, and Takeshi Tokuyama. Efficient algorithms for optimization-based image segmentation. International Journal of Computational Geometry and Applications, 11(2):145-166, 2001.
-
Man-Kwun Chiu and Matias Korman. High dimensional consistent digital segments. SIAM Journal on Discrete Mathematics, 32(4):2566-2590, 2018.
- Man-Kwun Chiu, Matias Korman, Martin Suderland, and Takeshi Tokuyama. Distance bounds for high dimensional consistent digital rays and 2-d partially-consistent digital rays, 2020. URL: http://arxiv.org/abs/2006.14059.
-
Iffat Chowdhury and Matt Gibson. A characterization of consistent digital line segments in ℤ². In Nikhil Bansal and Irene Finocchi, editors, Proceedings of the 23rd Annual European Symposium on Algorithms, volume 9294, pages 337-348, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
-
Iffat Chowdhury and Matt Gibson. Constructing consistent digital line segments. In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, Proceedings of the 12th Latin American Theoretical Informatics Symposium, volume 9644, pages 263-274, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.
-
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, Natsuda Kaothanthong, Ryosei Kasai, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama. Algorithms for computing the maximum weight region decomposable into elementary shapes. Computer Vision and Image Understanding, 116(7):803-814, 2012.
-
Jinhee Chun, Matias Korman, Martin Nöllenburg, and Takeshi Tokuyama. Consistent digital rays. Discrete and Computational Geometry, 42(3):359-378, 2009.
-
Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels. Coordinate representation of order types requires exponential storage. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 405-410. ACM, 1989.
-
Reinhard Klette and Azriel Rosenfeld. Digital straightness - a review. Discrete Appl. Math., 139(1-3):197-230, 2004.
-
Michael 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.
- Jiří Matoušek. Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics. Springer Berlin Heidelberg, 1999. URL: https://books.google.co.jp/books?id=BKvXj1GisP0C.
- Wolfgang Schmidt. Irregularities of distribution, vii. Acta Arithmetica, 21(1):45-50, 1972. URL: http://eudml.org/doc/205130.