{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:26Z","timestamp":1740109586744,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T00:00:00Z","timestamp":1647302400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T00:00:00Z","timestamp":1647302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC StG 757609"],"award-info":[{"award-number":["ERC StG 757609"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MEXT Kakenhi","award":["17K19954","18H05291"],"award-info":[{"award-number":["17K19954","18H05291"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {Z}^d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>Z<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The construction must be <jats:italic>consistent<\/jats:italic> (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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varTheta (\\log N)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> error, where resemblance between segments is measured with the Hausdorff distance, and <jats:italic>N<\/jats:italic> is the <jats:inline-formula><jats:alternatives><jats:tex-math>$$L_1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> distance between the two points. This construction was considered tight because of a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (\\log N)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> lower bound that applies to any consistent construction in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {Z}^2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>Z<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. 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 <jats:italic>d<\/jats:italic> dimensions must have <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varOmega (\\log ^{1\/(d-1)}\\!N)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>d<\/mml:mi>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mspace\/>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> error. We tie the error of a consistent construction in high dimensions to the error of similar <jats:italic>weak<\/jats:italic> 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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$o(\\log N)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>o<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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. A side result, that we find of independent interest, is the introduction of the <jats:italic>bichromatic discrepancy<\/jats:italic>: a natural extension of the concept of discrepancy of a set of points. In this paper, we define this concept and extend known results to the chromatic setting.<\/jats:p>","DOI":"10.1007\/s00454-021-00349-6","type":"journal-article","created":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T14:05:24Z","timestamp":1647353124000},"page":"902-944","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7435-1020","authenticated-orcid":false,"given":"Man-Kwun","family":"Chiu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matias","family":"Korman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6604-6381","authenticated-orcid":false,"given":"Martin","family":"Suderland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Tokuyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,15]]},"reference":[{"issue":"2","key":"349_CR1","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1142\/S0218195901000420","volume":"11","author":"T Asano","year":"2001","unstructured":"Asano, T., Chen, D.Z., Katoh, N., Tokuyama, T.: Efficient algorithms for optimization-based image segmentation. Int. J. Comput. Geom. Appl. 11(2), 145\u2013166 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"349_CR2","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02579453","volume":"1","author":"J Beck","year":"1981","unstructured":"Beck, J.: Balanced two-colorings of finite sets in the square. I. Combinatorica 1(4), 327\u2013335 (1981)","journal-title":"Combinatorica"},{"key":"349_CR3","doi-asserted-by":"crossref","unstructured":"Bodwin, G.: On the structure of unique shortest paths in graphs. In: 30th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (San Diego 2019), pp. 2071\u20132089. SIAM, Philadelphia (2019)","DOI":"10.1137\/1.9781611975482.125"},{"issue":"4","key":"349_CR4","doi-asserted-by":"publisher","first-page":"2566","DOI":"10.1137\/17M1136572","volume":"32","author":"M-K Chiu","year":"2018","unstructured":"Chiu, M.-K., Korman, M.: High dimensional consistent digital segments. SIAM J. Discrete Math. 32(4), 2566\u20132590 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"349_CR5","doi-asserted-by":"crossref","unstructured":"Chowdhury, I., Gibson, M.: A characterization of consistent digital line segments in $${\\mathbb{Z}}^2$$. In: 23rd Annual European Symposium on Algorithms (Patras 2015). Lecture Notes in Computer Science, vol. 9294, pp. 337\u2013348. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-48350-3_29"},{"key":"349_CR6","doi-asserted-by":"crossref","unstructured":"Chowdhury, I., Gibson, M.: Constructing consistent digital line segments. In: 12th Latin American Symposium on Theoretical Informatics (Ensenada 2016). Lecture Notes in Computer Science, vol. 9644, pp. 263\u2013274. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-49529-2_20"},{"issue":"4","key":"349_CR7","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s00454-012-9411-y","volume":"47","author":"T Christ","year":"2012","unstructured":"Christ, T., P\u00e1lv\u00f6lgyi, D., Stojakovi\u0107, M.: Consistent digital line segments. Discrete Comput. Geom. 47(4), 691\u2013710 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"7","key":"349_CR8","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1016\/j.cviu.2012.03.003","volume":"116","author":"J Chun","year":"2012","unstructured":"Chun, J., Kaothanthong, N., Kasai, R., Korman, M., N\u00f6llenburg, M., Tokuyama, T.: Algorithms for computing the maximum weight region decomposable into elementary shapes. Comput. Vis. Image Underst. 116(7), 803\u2013814 (2012)","journal-title":"Comput. Vis. Image Underst."},{"issue":"3","key":"349_CR9","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00454-009-9166-2","volume":"42","author":"J Chun","year":"2009","unstructured":"Chun, J., Korman, M., N\u00f6llenburg, M., Tokuyama, T.: Consistent digital rays. Discrete Comput. Geom. 42(3), 359\u2013378 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"349_CR10","doi-asserted-by":"crossref","unstructured":"Cizma, D., Linial, N.: Geodesic geometry on graphs. Discrete Comput. Geom. (2022). https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00345-w","DOI":"10.1007\/s00454-021-00345-w"},{"issue":"3","key":"349_CR11","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1006\/jcss.1996.0034","volume":"52","author":"DP Dobkin","year":"1996","unstructured":"Dobkin, D.P., Gunopulos, D., Maass, W.: Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning. J. Comput. Syst. Sci. 52(3), 453\u2013470 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"349_CR12","doi-asserted-by":"crossref","unstructured":"Goodman, J.E., Pollack, R., Sturmfels, B.: Coordinate representation of order types requires exponential storage. In: 21st Annual ACM Symposium on Theory of Computing (Seattle 1989), pp. 405\u2013410. ACM, New York (1989)","DOI":"10.1145\/73007.73046"},{"issue":"1\u20133","key":"349_CR13","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.dam.2002.12.001","volume":"139","author":"R Klette","year":"2004","unstructured":"Klette, R., Rosenfeld, A.: Digital straightness\u2014a review. Discrete Appl. Math. 139(1\u20133), 197\u2013230 (2004)","journal-title":"Discrete Appl. Math."},{"key":"349_CR14","doi-asserted-by":"crossref","unstructured":"Luby, M.G.: Grid geometries which preserve properties of Euclidean geometry: a study of graphics line drawing algorithms. In: Theoretical Foundations of Computer Graphics and CAD (Il Ciocco 1987). NATO Advanced Science Institutes Series, vol. F40, pp. 397\u2013432. Springer, Berlin (1987)","DOI":"10.1007\/978-3-642-83539-1_15"},{"key":"349_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03942-3","volume-title":"Geometric Discrepancy. Algorithms and Combinatorics","author":"J Matou\u0161ek","year":"1999","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy. Algorithms and Combinatorics, vol. 18. Springer, Berlin (1999)"},{"key":"349_CR16","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/aa-21-1-45-50","volume":"21","author":"WM Schmidt","year":"1972","unstructured":"Schmidt, W.M.: Irregularities of distribution, VII. Acta Arith. 21, 45\u201350 (1972)","journal-title":"Acta Arith."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00349-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00349-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00349-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T19:03:48Z","timestamp":1663009428000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00349-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,15]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["349"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00349-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,3,15]]},"assertion":[{"value":"7 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}