Document Open Access Logo

High Quality Consistent Digital Curved Rays via Vector Field Rounding

Authors Takeshi Tokuyama, Ryo Yoshimura

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.58.pdf
  • Filesize: 1.07 MB
  • 17 pages

Document Identifiers

Author Details

Takeshi Tokuyama
  • Department of Computer Science, School of Engineering, Kwansei Gakuin University, Sanda, Japan
Ryo Yoshimura
  • Graduate School of Information Science and Technology, The University of Tokyo, Japan

Funding

This work was supported by JSPS KAKENHI Grant Number 20H04143.

Cite AsGet BibTex

Takeshi Tokuyama and Ryo Yoshimura. High Quality Consistent Digital Curved Rays via Vector Field Rounding. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.58

Abstract

We consider the consistent digital rays (CDR) of curved rays, which approximates a set of curved rays emanating from the origin by the set of rooted paths (called digital rays) of a spanning tree of a grid graph. Previously, a construction algorithm of CDR for diffused families of curved rays to attain an O(√{n log n}) bound for the distance between digital ray and the corresponding ray is known [Chun et al., 2019]. In this paper, we give a description of the problem as a rounding problem of the vector field generated from the ray family, and investigate the relation of the quality of CDR and the discrepancy of the range space generated from gradient curves of rays. Consequently, we show the existence of a CDR with an O(log ^{1.5} n) distance bound for any diffused family of curved rays.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Computational Geometry
  • Discrepancy Theory
  • Consistent Digital Rays
  • Digital Geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. C. Aistleitner, D. Bilyk, and A. Nikolov. Tusnády’s problem, the transference principle, and non-uniform QMC sampling. In International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, pages 169-180. Springer, 2016. Google Scholar
  2. N. Bansal, D. Dadush, and S. Garg. An algorithm for Komlós conjecture matching Banaszczyk’s bound. SIAM J. Comput., 48(2):534-553, 2019. URL: https://doi.org/10.1137/17M1126795.
  3. N. Bansal and S. Garg. Algorithmic discrepancy beyond partial coloring. In Proc. 49th ACM Symposium on Theory of Computing, pages 914-926, 2017. Google Scholar
  4. J. Beck. Balanced two-colorings of finite sets in the square I. Combinatorica, 1(4):327-335, 1981. Google Scholar
  5. J. Beck and V. T. Toth. Discrepancy Theory. Handbook of Combinatorics, 2(Chapter 26):1406-1446, 1996. Google Scholar
  6. G. Bohus. On the discrepancy of 3 permutations. Random Structures & Algorithms, 1(2):215-220, 1990. Google Scholar
  7. M.-K. Chiu, K. Korman, M. Suderland, and T. Tokuyama. Distance bounds for high dimensional consistent digital rays and 2-d partially-consistent digital rays. In Proc. 28th European Symposium on Algorithms, pages 34:1-34:22, 2020. Google Scholar
  8. I. Chowdhury and M Gibson. A characterization of consistent digital line segments in Z². In Proc. 23rd European Symposium on Algorithms, pages 337-348, 2015. Google Scholar
  9. I. Chowdhury and M Gibson. Constructing consistent digital line segments. In Proc. 12th Latin American Theoretical Informatics Conference, pages 263-274, 2016. Google Scholar
  10. T. Christ, D. Pálvölgyi, and M. Stojaković. Consistent digital line segment. Discrete & Computational Geometry, 47-4:691-710, 2012. Google Scholar
  11. J. Chun, K. Kikuchi, and T. Tokuyama. Consistent digital curved rays and pseudoline arrangements. In Proc. 27th European Symposium on Algorithms, pages 32:1-32:16, 2019. Google Scholar
  12. J. Chun, M. Korman, M. Nöllenburg, and T. Tokuyama. Consistent digital rays. Discrete & Computational Geometry, 42-3:359-378, 2009. Google Scholar
  13. Kunal Dutta. On shallow packings and Tusnády’s problem. CoRR, abs/2109.05693, 2021. URL: http://arxiv.org/abs/2109.05693.
  14. R. Klette and A. Rosenfeld. Digital straightness - a review. Discrete Applied Math., 139:197-230, 2004. Google Scholar
  15. 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. Google Scholar
  16. J. Matoušek. Geometric discrepancy: An illustrated guide. Springer Science & Business Media, 1999. Google Scholar
  17. A. Nikolov. Tighter bounds for the discrepancy of boxes and polytopes. Mathematika, 63(3):1091-1113, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact