{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T03:48:18Z","timestamp":1780458498763,"version":"3.54.1"},"reference-count":59,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:00:00Z","timestamp":1559001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Space-filling curves (SFCs) represent an efficient and straightforward method for sparse-space indexing to transform an n-dimensional space into a one-dimensional representation. This is often applied for multidimensional point indexing which brings a better perspective for data analysis, visualization and queries. SFCs are involved in many areas such as big data analysis and visualization, image decomposition, computer graphics and geographic information systems (GISs). The indexing methods subdivide the space into logic clusters of close points and they differ in various parameters including the cluster order, the distance metrics, and the pattern shape. Beside the simple and highly preferred triangular and square uniform grids, the hexagonal uniform grids have gained high interest especially in areas such as GISs, image processing and data visualization for the uniform distance between cells and high effectiveness of circle coverage. While the linearization of hexagons is an obvious approach for memory representation, it seems there is no hexagonal SFC indexing method generally used in practice. The main limitation of hexagons lies in lacking infinite decomposition into sub-hexagons and similarity of tiles on different levels of hierarchy. Our research aims at defining a fast and robust hexagonal SFC method. The Gosper fractal is utilized to preserve the benefits of hexagonal grids and to efficiently and hierarchically linearize points in a hexagonal grid while solving the non-convex shape and recursive transformation issues of the fractal. A comparison to other SFCs and grids is conducted to verify the robustness and effectiveness of our hexagonal method.<\/jats:p>","DOI":"10.3390\/sym11060731","type":"journal-article","created":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T11:18:09Z","timestamp":1559042289000},"page":"731","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["Hierarchical Hexagonal Clustering and Indexing"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7475-3625","authenticated-orcid":false,"given":"Vojt\u011bch","family":"Uher","sequence":"first","affiliation":[{"name":"Department of Computer Science, V\u0160B-Technical University of Ostrava, Ostrava-Poruba 708 00, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr","family":"Gajdo\u0161","sequence":"additional","affiliation":[{"name":"Department of Computer Science, V\u0160B-Technical University of Ostrava, Ostrava-Poruba 708 00, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V\u00e1clav","family":"Sn\u00e1\u0161el","sequence":"additional","affiliation":[{"name":"Department of Computer Science, V\u0160B-Technical University of Ostrava, Ostrava-Poruba 708 00, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8578-3101","authenticated-orcid":false,"given":"Yu-Chi","family":"Lai","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University of Science and Technology, 43, Sec.4, Keelung Rd., Taipei 106, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Radeck\u00fd","sequence":"additional","affiliation":[{"name":"Department of Computer Science, V\u0160B-Technical University of Ostrava, Ostrava-Poruba 708 00, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,5,28]]},"reference":[{"key":"ref_1","unstructured":"Bader, M. (2012). Space-Filling Curves: An Introduction with Applications in Scientific Computing, Springer Publishing Company, Incorporated."},{"key":"ref_2","unstructured":"Lawder, J.K., and King, P.J.H. (2000). Using Space-Filling Curves for Multi-dimensional Indexing. Proceedings of the 17th British National Conferenc on Databases: Advances in Databases, Springer."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/j.is.2004.12.001","article-title":"A New Range Query Algorithm for Universal B-trees","volume":"31","author":"Skopal","year":"2006","journal-title":"Inf. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1111\/j.1467-8659.2009.01377.x","article-title":"Fast BVH Construction on GPUs","volume":"28","author":"Lauterbach","year":"2009","journal-title":"Comput. Graph. Forum"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Isaac, T., Burstedde, C., and Ghattas, O. (2012, January 21\u201325). Low-Cost Parallel Algorithms for 2:1 Octree Balance. Proceedings of the 2012 IEEE 26th International Parallel Distributed Processing Symposium (IPDPS), Shanghai, China.","DOI":"10.1109\/IPDPS.2012.47"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1038\/scientificamerican1276-124","article-title":"Mathematical Games\u2014In which \u201cmonster\u201d curves force redefinition of the word \u201ccurve\u201d","volume":"235","author":"Gardner","year":"1976","journal-title":"Sci. Am."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Uher, V., Gajdo\u0161, P., Radeck\u00fd, M., and Sn\u00e1\u0161el, V. (2016, January 9\u201312). A proposal of hierarchical vertex clustering based on the Gosper curve. Proceedings of the 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Budapest, Hungary.","DOI":"10.1109\/SMC.2016.7844311"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Uher, V., Gajdo\u0161, P., and Sn\u00e1\u0161el, V. (2017, January 21\u201323). Towards the Gosper Space Filling Curve Implementation. Proceedings of the 2017 3rd IEEE International Conference on Cybernetics (CYBCONF), Exeter, UK.","DOI":"10.1109\/CYBConf.2017.7985819"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Rusu, R.B., and Cousins, S. (2011, January 9\u201313). 3D is here: Point Cloud Library (PCL). Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China.","DOI":"10.1109\/ICRA.2011.5980567"},{"key":"ref_10","unstructured":"Samet, H. (2005). Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann Publishers Inc."},{"key":"ref_11","unstructured":"Brodsky, I. (2019, April 20). H3: Uber\u2019s Hexagonal Hierarchical Spatial Index. Available online: https:\/\/eng.uber.com\/h3\/."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.swevo.2015.07.006","article-title":"A parallel Fruchterman\u2013Reingold algorithm optimized for fast visualization of large graphs and swarms of data","volume":"26","author":"Uher","year":"2016","journal-title":"Swarm Evol. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Uher, V., Gajdo\u0161, P., and Je\u017eowicz, T. (2015, January 24\u201326). Solving nearest neighbors problem on GPU to speed up the Fruchterman-Reingold graph layout algorithm. Proceedings of the 2015 IEEE 2nd International Conference on Cybernetics (CYBCONF), Gdynia, Poland.","DOI":"10.1109\/CYBConf.2015.7175951"},{"key":"ref_14","unstructured":"Pharr, M., Jakob, W., and Humphreys, G. (2016). Physically Based Rendering: From Theory to Implementation, Morgan Kaufmann."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Langetepe, E., and Zachmann, G. (2006). Geometric Data Structures for Computer Graphics, AK Peters, Ltd.","DOI":"10.1201\/9780367803735"},{"key":"ref_16","unstructured":"Sonka, M., Hlav\u00e1\u010d, V., and Boyle, R. (2014). Image Processing, Analysis, and Machine Vision, Cengage Learning."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/0734-189X(83)90043-9","article-title":"On approaches to polygonal decomposition for hierarchical image representation","volume":"24","author":"Ahuja","year":"1983","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"ref_18","unstructured":"Middleton, L., and Sivaswamy, J. (2006). Hexagonal Image Processing: A practical Approach, Springer. Advances in Computer Vision and Pattern Recognitio."},{"key":"ref_19","first-page":"363","article-title":"Hexagonal discrete global grid systems for geospatial computing","volume":"22","author":"Sahr","year":"2011","journal-title":"Arch. Photogramm. Cartogr. Remote Sens."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Ben, J., Tong, X., and Chen, R. (2010, January 18\u201320). A spatial indexing method for the hexagon discrete global grid system. Proceedings of the 2010 18th International Conference on Geoinformatics, Beijing, China.","DOI":"10.1109\/GEOINFORMATICS.2010.5567972"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1080\/17538947.2014.927597","article-title":"Hexagonal connectivity maps for Digital Earth","volume":"8","author":"Harrison","year":"2015","journal-title":"Int. J. Digit. Earth"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"320","DOI":"10.3390\/ijgi4010320","article-title":"Categorization and Conversions for Indexing Methods of Discrete Global Grid Systems","volume":"4","author":"Samavati","year":"2015","journal-title":"ISPRS Int. J. Geo-Inf."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.cad.2016.04.005","article-title":"Hierarchical Grid Conversion","volume":"79","author":"Harrison","year":"2016","journal-title":"Comput. Aided Des."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Wang, D., Xu, L., Peng, J., and Robila, S. (2009, January 6\u20138). Subdividing Hexagon-Clustered Wireless Sensor Networks for Power-Efficiency. Proceedings of the 2009 WRI International Conference on Communications and Mobile Computing, Kunming, China.","DOI":"10.1109\/CMC.2009.317"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2011\/940751","article-title":"A Top-Down Clustering and Cluster-Tree-Based Routing Scheme for Wireless Sensor Networks","volume":"7","author":"Bandara","year":"2011","journal-title":"Int. J. Distrib. Sens. Netw."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.cam.2018.06.029","article-title":"Hamiltonian triangular refinements and space-filling curves","volume":"346","author":"Plaza","year":"2019","journal-title":"J. Comput. Appl. Math."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.cag.2015.07.019","article-title":"Rapid Delaunay triangulation for randomly distributed point cloud data using adaptive Hilbert curve","volume":"54","author":"Su","year":"2016","journal-title":"Comput. Graph."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.cagd.2003.08.001","article-title":"A generative classification of mesh refinement rules with lattice transformations","volume":"21","author":"Ivrissimtzis","year":"2004","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S0167-8396(02)00084-5","article-title":"Refinement operators for triangle meshes","volume":"19","author":"Alexa","year":"2002","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_30","unstructured":"Franklin, W.R. (2005, January 10\u201312). Nearest Point Query on 184M Points in E3 with a Uniform Grid. Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG\u201905), Windsor, ON, Canada."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","article-title":"External Memory Algorithms and Data Structures: Dealing with Massive Data","volume":"33","author":"Vitter","year":"2001","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/S0022-0000(69)80010-3","article-title":"Convergence with Hilbert\u2019s Space Filling Curve","volume":"3","author":"Butz","year":"1969","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_33","unstructured":"Lam, W.M., and Shapiro, J.M. (1994, January 13\u201316). A Class of Fast Algorithms for the Peano-Hilbert Space-Filling Curve. Proceedings of the 1st International Conference on Image Processing, Austin, TX, USA."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1145\/290200.290219","article-title":"Algorithm 781: Generating Hilbert\u2019s Space-Filling Curve by Recursion","volume":"24","author":"Breinholt","year":"1998","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1016\/S0262-8856(01)00067-1","article-title":"Edge detection in a hexagonal-image processing framework","volume":"19","author":"Middleton","year":"2001","journal-title":"Image Vis. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Ohn, S.Y. (2006). Neighborhood Decomposition of Convex Structuring Elements for Mathematical Morphology on Hexagonal Grid. Proceedings of the 21st International Conference on Computer and Information Sciences, Springer.","DOI":"10.1007\/11902140_55"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0262-8856(83)90020-3","article-title":"Spatially referenced methods of processing raster and vector data","volume":"1","author":"Bell","year":"1983","journal-title":"Image Vis. Comput."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0146-664X(80)90056-8","article-title":"Tree and pyramid structures for coding hexagonally sampled binary images","volume":"14","author":"Burt","year":"1980","journal-title":"Comput. Graph. Image Process."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0146-664X(82)90075-2","article-title":"Vectorization of raster images using hierarchical methods","volume":"20","author":"Gibson","year":"1982","journal-title":"Comput. Graph. Image Process."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1016\/j.jvcir.2006.04.003","article-title":"Indexing the aperture 3 hexagonal discrete global grid","volume":"17","author":"Vince","year":"2006","journal-title":"J. Vis. Commun. Image Represent."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.5194\/isprsarchives-XL-4-W2-1-2013","article-title":"On the Optimal Representation of Vector Location using Fixed-Width Multi-Precision Quantizers","volume":"XL-4\/W2","author":"Sahr","year":"2013","journal-title":"ISPRS-Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_42","first-page":"92","article-title":"Recursive tilings and space-filling curves with little fragmentation","volume":"2","author":"Haverkort","year":"2011","journal-title":"J. Comput. Geom."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-319-28031-8_18","article-title":"Application of Hexagonal Coordinate Systems for Searching the K-NN in 2D Space","volume":"Volume 424","author":"Uher","year":"2016","journal-title":"Innovations in Bio-Inspired Computing and Applications"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1301","DOI":"10.1109\/TVCG.2008.158","article-title":"Rapid Graph Layout Using Space Filling Curves","volume":"14","author":"Muelder","year":"2008","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1820","DOI":"10.1109\/TVCG.2013.91","article-title":"GosperMap: Using a Gosper Curve for Laying Out Hierarchical Data","volume":"19","author":"Auber","year":"2013","journal-title":"Vis. Comput. Graph. IEEE Trans."},{"key":"ref_46","unstructured":"Wyvill, B. (2015). Painting with Flowsnakes. Proceedings of the Workshop on Computational Aesthetics, Eurographics Association."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s004540010071","article-title":"The honeycomb conjecture","volume":"25","author":"Hales","year":"2001","journal-title":"Discret. Comput. Geom."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Mandelbrot, B.B. (1983). The Fractal Geometry of Nature, W. H. Freeman and Co.","DOI":"10.1119\/1.13295"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/j.comgeo.2009.06.002","article-title":"Locality and bounding-box quality of two-dimensional space-filling curves","volume":"43","author":"Haverkort","year":"2010","journal-title":"Comput. Geom."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1080\/00029890.2005.11920227","article-title":"The Isoperimetric Problem","volume":"112","year":"2005","journal-title":"Am. Math. Mon."},{"key":"ref_51","unstructured":"Chang, H.C., and Wang, L.C. (2010). A simple proof of Thue\u2019s Theorem on circle packing. arXiv."},{"key":"ref_52","unstructured":"Patel, A.J. (2019, March 20). Red Blob Games\u2014Hexagonal Grids. Available online: http:\/\/www.redblobgames.com\/grids\/hexagons\/."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"2825","DOI":"10.1016\/j.jcp.2011.12.024","article-title":"A Sparse Octree Gravitational N-body Code That Runs Entirely on the GPU Processor","volume":"231","author":"Gaburov","year":"2012","journal-title":"J. Comput. Phys."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1559\/152304003100011090","article-title":"Geodesic Discrete Global Grid Systems","volume":"30","author":"Sahr","year":"2003","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_55","unstructured":"Smith, W.D. (2019, March 20). Space-filling curves, Randomness, and Geometry Problems. Available online: http:\/\/rangevoting.org\/SpaceFillCurve.html."},{"key":"ref_56","unstructured":"Ventrella, J. (2019, March 20). Brainfilling Curves\u2014The Root 7 Family. Available online: http:\/\/www.fractalcurves.com\/Root7.html."},{"key":"ref_57","unstructured":"Riddle, L. (2019, March 20). Classic Iterated Function Systems\u2014Flowsnake. Available online: http:\/\/ecademy.agnesscott.edu\/~lriddle\/ifs\/ksnow\/flowsnake.htm."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1006\/jfan.1996.2928","article-title":"The Dimension of the Brownian Frontier is Greater Than 1","volume":"143","author":"Bishop","year":"1997","journal-title":"J. Funct. Anal."},{"key":"ref_59","unstructured":"Fr\u00e4nti, P. (2019, March 20). Clustering Basic Benchmark. Available online: https:\/\/cs.joensuu.fi\/sipu\/datasets\/."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/6\/731\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:54:05Z","timestamp":1760187245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/6\/731"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,28]]},"references-count":59,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["sym11060731"],"URL":"https:\/\/doi.org\/10.3390\/sym11060731","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,28]]}}}