Voronoi treemap in Manhattan distance and Chebyshev distance. (July 2023)
- Record Type:
- Journal Article
- Title:
- Voronoi treemap in Manhattan distance and Chebyshev distance. (July 2023)
- Main Title:
- Voronoi treemap in Manhattan distance and Chebyshev distance
- Authors:
- Wang, Yan Chao
Xing, Yidan
Zhang, Jie - Abstract:
- 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 ±45° to thex -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's 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. TheThe 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 ±45° to thex -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's 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. … (more)
- Is Part Of:
- Information visualization. Volume 22:Number 3(2023)
- Journal:
- Information visualization
- Issue:
- Volume 22:Number 3(2023)
- Issue Display:
- Volume 22, Issue 3 (2023)
- Year:
- 2023
- Volume:
- 22
- Issue:
- 3
- Issue Sort Value:
- 2023-0022-0003-0000
- Page Start:
- 246
- Page End:
- 264
- Publication Date:
- 2023-07
- Subjects:
- Voronoi treemap -- Manhattan distance -- Chebyshev distance -- weighted Voronoi treemap -- implicit hierarchy visualization
Information visualization -- Periodicals
006.605 - Journal URLs:
- http://ivi.sagepub.com/ ↗
http://www.palgrave-journals.com/ivs/index.html ↗
http://www.uk.sagepub.com ↗ - DOI:
- 10.1177/14738716231167181 ↗
- Languages:
- English
- ISSNs:
- 1473-8716
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 4496.401000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 26920.xml