DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2022.58

High Quality Consistent Digital Curved Rays via Vector Field Rounding

Authors: Takeshi Tokuyama and Ryo Yoshimura

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{tokuyama_et_al:LIPIcs.STACS.2022.58,
  author =	{Tokuyama, Takeshi and Yoshimura, Ryo},
  title =	{{High Quality Consistent Digital Curved Rays via Vector Field Rounding}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{58:1--58:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.58},
  URN =		{urn:nbn:de:0030-drops-158680},
  doi =		{10.4230/LIPIcs.STACS.2022.58},
  annote =	{Keywords: Computational Geometry, Discrepancy Theory, Consistent Digital Rays, Digital Geometry}
}

Search Results

Documents authored by Yoshimura, Ryo

High Quality Consistent Digital Curved Rays via Vector Field Rounding

Abstract

Cite as

Thanks for your feedback!

Could not send message