LIPIcs.SoCG.2020.81.pdf
- Filesize: 4.56 MB
- 5 pages
Document
Plane-Filling Trails (Media Exposition)
Author
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
Cite AsGet BibTex
Herman Haverkort. Plane-Filling Trails (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 81:1-81:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.81
https://doi.org/10.4230/LIPIcs.SoCG.2020.81
Abstract
The order in which plane-filling curves visit points in the plane can be exploited to design efficient algorithms. Typically, the curves are useful because they preserve locality: points that are close to each other along the curve tend to be close to each other in the plane, and vice versa. However, sketches of plane-filling curves do not show this well: they are hard to read on different levels of detail and it is hard to see how far apart points are along the curve. This paper presents a software tool to produce compelling visualisations that may give more insight in the structure of the curves.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- space-filling curve
- plane-filling curve
- spatial indexing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
M. Bader. Space-filling curves: an introduction with applications in scientific computing. Springer, 2013.
-
C. Bandt, D. Mekhontsev, and A. Tetenov. A single fractal pinwheel tile. Proc. Amer. Math,. Soc., 146:1271-1285, 2018.
-
C. Burstedde and J. Holke. A tetrahedral space-filling curve for nonconforming adaptive meshes. SIAM J. Scientific Computing, 38(5), 2016.
-
C. Faloutsos. Multiattribute hashing using Gray codes. In Proc. 1986 Conf. ACM SIG Management of Data (SIGMOD 1986), pages 227-238, 1986.
-
M. Gardner. Mathematical games: in which "monster" curves force redefinition of the word "curve". Scientific American, 235:124-133, 1976.
- H. Haverkort. Sixteen space-filling curves and traversals for d-dimensional cubes and simplices. CoRR, abs/1711.04473, 2017. URL: http://arxiv.org/abs/1711.04473.
-
D. Hilbert. Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann., 38(3):459-460, 1891.
-
G. Irving and H. Segerman. Developing fractal curves. J. of Mathematics and the Arts, 7(3-4):103-121, 2013.
-
G. Morton. A computer oriented geodetic data base, and a new technique in file sequencing. Technical report, International Business Machines Co., Ottawa, Canada, 1966.
- S. Ortiz. Hilbert curve marble run, 2018. Accessed 26 March 2020. URL: https://www.thingiverse.com/thing:3031891.
-
G. Peano. Sur une courbe, qui remplit toute une aire plane. Math. Ann., 36(1):157-160, 1890.
-
G. Pólya. Über eine Peanosche Kurve. Bull. Int. Acad. Sci. Cracovie, Ser. A, pages 305-313, 1913.
-
G. Rauzy. Nombres algébriques et substitutions. Bulletin Soc. Math. Fr., 110:147-178, 1982.
-
H. Samet. Foundations of multidimensional and metric data structures, page 199. Morgan Kaufmann, 2006.
-
J. Ventrella. Brainfilling curves: a fractal bestiary. Eyebrain books, 2012.
-
J.-M. Wierum. Definition of a new circular space-filling curve: βΩ-indexing. Technical Report TR-001-02, Paderborn Center for Parallel Computing (PC²), 2002.
-
S.-E. Yoon and P. Lindstrom. Mesh layouts for block-based caches. IEEE Trans. on Visualization and Computer Graphics, 12(5), 2006.