{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T03:19:01Z","timestamp":1777778341645,"version":"3.51.4"},"reference-count":50,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T00:00:00Z","timestamp":1681948800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Information Visualization"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>The ordinary Voronoi treemap generated based on the Euclidean distance function has the flexibility to slightly adjust the layout when visualizing time-varying hierarchical data for better visual quality, preserving neighborhood relationships, and preserving a stable layout. However, its layout formed by segments with arbitrary orientations has poor shape stability between successive layouts at different time indexes, which is not conducive for the users to understand the plot and track the same node. In this paper, we propose novel Voronoi treemaps in Manhattan distance and Chebyshev distance respectively, such that the segments in the new layouts only have four orientations (horizontal, vertical, and \u00b145\u00b0 to the [Formula: see text]-axis). The new layouts can not only heritage the abilities of ordinary Voronoi treemap, but preserve good shape stability. To achieve this, we first focus on the weighted bisector between two sites in Manhattan distance and design a bisector generation method for different weight values of two sites, as the bisector is the foundation to form a diagram. Then a divide-and-conquer method is utilized to form the bisectors into a Voronoi diagram, and a Voronoi treemap layout can be finally obtained by using Lloyd\u2019s method to iteratively adjust the diagram. Moreover, we prove that the treemap algorithm in Manhattan distance can be adjusted to also generate the Voronoi treemap in Chebyshev distance via linear transformation, avoiding designing additional algorithm. The computational properties of the proposed methods are first evaluated to check whether the layouts can be generated fast and accurately. Then the perceptual properties are evaluated quantitatively and qualitatively based on quality metrics and user studies, respectively. The results demonstrate that the proposed Voronoi treemaps preserve similar layout stability, but better visual quality and shape stability than the ordinary Voronoi treemap. Our algorithms are simple and resolution-independent, but also provide alternatives to the Voronoi treemaps.<\/jats:p>","DOI":"10.1177\/14738716231167181","type":"journal-article","created":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T01:33:20Z","timestamp":1682040800000},"page":"246-264","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":6,"title":["Voronoi treemap in Manhattan distance and Chebyshev distance"],"prefix":"10.1177","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5482-8626","authenticated-orcid":false,"given":"Yan Chao","family":"Wang","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yidan","family":"Xing","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2023,4,20]]},"reference":[{"key":"bibr1-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234212"},{"key":"bibr2-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1981.234519"},{"key":"bibr3-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1006\/jvlc.1996.0003"},{"key":"bibr4-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1145\/102377.115768"},{"key":"bibr5-14738716231167181","first-page":"49","volume-title":"Proc. INFOVIS","author":"Balzer M"},{"key":"bibr6-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1007\/s12650-022-00830-1"},{"key":"bibr7-14738716231167181","volume-title":"Proximity and Applications in General Metrics","author":"Gavrilova M.","year":"1998"},{"key":"bibr8-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778856"},{"key":"bibr9-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"bibr10-14738716231167181","first-page":"79","volume-title":"2009 sixth international symposium on Voronoi diagrams","author":"Balzer M"},{"key":"bibr11-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531392"},{"key":"bibr12-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.165"},{"key":"bibr13-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.108"},{"key":"bibr14-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2745140"},{"key":"bibr15-14738716231167181","first-page":"33","volume-title":"Data visualization","author":"Bruls M","year":"2000"},{"key":"bibr16-14738716231167181","first-page":"73","volume-title":"Proc. INFOVIS","author":"Shneiderman B"},{"key":"bibr17-14738716231167181","first-page":"73","volume-title":"Proceedings 1999 IEEE symposium on information visualization (InfoVis\u2019 99)","author":"Van Wijk JJ"},{"key":"bibr18-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2346276"},{"key":"bibr19-14738716231167181","first-page":"74","volume-title":"Proc. IV","author":"Liang J"},{"key":"bibr20-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1145\/2493102.2493112"},{"key":"bibr21-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1145\/2801040.2801056"},{"key":"bibr22-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvlc.2015.10.009"},{"key":"bibr23-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2743959"},{"key":"bibr24-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03078.x"},{"key":"bibr25-14738716231167181","first-page":"85","volume-title":"Proc. ISVD","author":"Sud A"},{"key":"bibr26-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/VISSOFT.2015.7332410"},{"key":"bibr27-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/SIBGRAPI.2018.00027"},{"key":"bibr28-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"bibr29-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1137\/0216006"},{"key":"bibr30-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(84)90064-5"},{"key":"bibr31-14738716231167181","first-page":"115","volume-title":"Proceedings of the Conference on computer graphics & visual computing","author":"Ahmed AG"},{"key":"bibr32-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322219"},{"key":"bibr33-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1137\/0209017"},{"key":"bibr34-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.185"},{"key":"bibr35-14738716231167181","volume-title":"Proceedings of the 12th conference on learning factories (CLF 2022)","author":"Wang YC"},{"key":"bibr36-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1080\/00207543.2017.1333649"},{"key":"bibr37-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13989"},{"key":"bibr38-14738716231167181","first-page":"181","volume-title":"Proc. INFOVIS","author":"Wattenberg M"},{"key":"bibr39-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.12.008"},{"key":"bibr40-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2346277"},{"key":"bibr41-14738716231167181","volume-title":"Proc. CGI","author":"Wang YC"},{"key":"bibr42-14738716231167181","first-page":"88","volume-title":"Proceedings of the 12th international joint conference on computer vision, imaging and computer graphics theory and applications -IVAPP, (VISIGRAPP 2017)","author":"Hahn S"},{"key":"bibr43-14738716231167181","author":"Feng C","year":"2019","journal-title":"Proc Computational Visual Media (CVM\u201919)"},{"issue":"2","key":"bibr44-14738716231167181","first-page":"150","volume":"30","author":"Gotz D.","year":"2011","journal-title":"Phys Rev A"},{"key":"bibr45-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2017.12.136"},{"key":"bibr46-14738716231167181","first-page":"1","volume-title":"Proceedings of the 13th international symposium on visual information communication and interaction","author":"Fiedler C"},{"key":"bibr47-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2424889"},{"key":"bibr48-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2021.3064037"},{"key":"bibr49-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1002\/col.22196"},{"key":"bibr50-14738716231167181","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.79"}],"container-title":["Information Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/14738716231167181","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/14738716231167181","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/14738716231167181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:19:16Z","timestamp":1777490356000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/14738716231167181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,20]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.1177\/14738716231167181"],"URL":"https:\/\/doi.org\/10.1177\/14738716231167181","relation":{},"ISSN":["1473-8716","1473-8724"],"issn-type":[{"value":"1473-8716","type":"print"},{"value":"1473-8724","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,20]]}}}