LIPIcs.ESA.2019.32.pdf
- Filesize: 0.8 MB
- 16 pages
Document
Consistent Digital Curved Rays and Pseudoline Arrangements
Authors
-
Part of:
Volume:
27th Annual European Symposium on Algorithms (ESA 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-06
Cite As Get BibTex
Jinhee Chun, Kenya Kikuchi, and Takeshi Tokuyama. Consistent Digital Curved Rays and Pseudoline Arrangements. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.32
Abstract
Representing a family of geometric objects in the digital world where each object is represented by a set of pixels is a basic problem in graphics and computational geometry. One important criterion is the consistency, where the intersection pattern of the objects should be consistent with axioms of the Euclidean geometry, e.g., the intersection of two lines should be a single connected component. Previously, the set of linear rays and segments has been considered. In this paper, we extended this theory to families of curved rays going through the origin. We further consider some psudoline arrangements obtained as unions of such families of rays.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Computational Geometry
- Digital Geometry
- Spanning Tree
- Graph Drawing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
M. Chiu, M. Korman, M. Sutherland, and T. Tokuyama. Distance bounds for 3-D consistent digital rays and 2-D partially-consistent digital rays. In preparation.
-
I. Chowdhury and M Gibson. A Characterization of Consistent Digital Line Segments in Z². In Proc. 23rd ESA, pages 337-348, 2015.
-
I. Chowdhury and M Gibson. Constructing Consistent Digital Line Segments. In Proc. 12th LATIN, pages 263-274, 2016.
-
T. Christ, D. Pálvölgyi, and M. Stojaković. Consistent Digital Line Segment. Discrete & Computational Geometry, 47-4:691-710, 2012.
-
J. Chun, M. Korman, M. Nöllenburg, and T. Tokuyama. Consistent Digital Rays. Discrete & Computational Geometry, 42-3:359-378, 2009.
-
F.P.Preparata and M.I.Shamos. Computational Geometry - an Introduction. Springer Verlag, 1985.
-
D. Greene and F. Yao. Finite Resolutional Computational Geometry. In Proc. 27th IEEE FOCS, pages 143-152, 1986.
-
D. Halperin and E. Packer. Iterated Snap Rounding. Comput. Geom. Theor. Appl., 23:209-225, 2002.
-
J. Hershberger. Stable Snap Rounding. Comput. Geom. Theor. Appl., 46:403-416, 2013.
-
J. Hobby. Practical Segment Intersection with Finite Precision Output. Comput. Geom. Theor. Appl., 13:199-214, 1999.
-
R. Klette and A. Rosenfeld. Digital straightness - a review. Discrete Applied Math., 139:197-230, 2004.
-
J. Matousěk. Geometric Discrepancy. Springer Verlag, 1991.
-
K. Mehlhorn and S. Näher. LEDA: a platform for combinatorial and geometric computation. Cambridge University Press, 1999.
-
M.G.Lubby. 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.
-
V. Milenkovic. Double Precision Geometry: A General Technique for Calculating Lines and Segment Intersections using Rounding Arithmetic. In Proc. 30th IEEE FOCS, pages 500-505, 1989.
-
H. Niederreiter. Recent constructions of low-discrepancy sequences. Mathematics and Computers in Simulation, 135:18-27, 2017.