Neighborhood-Preserving Voronoi Treemaps

Patrick Paetzold, Rebecca Kehlbeck, Yumeng Xue, Bin Chen, Yunhai Wang, Oliver Deußen

Abstract

Traditional Voronoi treemaps excel at representing hierarchical data structures through organic, space-filling polygonal partitions. However, they typically fail to account for non-hierarchical relationships—secondary similarities that exist between data points across different branches of a tree. This paper introduces a novel Voronoi treemap algorithm designed to preserve these neighborhood relationships. By integrating similarity constraints into every stage of the visualization pipeline—from initialization to a force-based optimization—the proposed method ensures that "similar" items become geometric neighbors, providing a more intuitive and context-aware data representation.

Introduction

Treemaps are a fundamental tool for visualizing hierarchical data, such as file systems, taxonomies, or corporate structures. Voronoi treemaps, in particular, offer an organic aesthetic by utilizing polygons rather than rigid rectangles. Despite their visual appeal, standard Voronoi treemaps suffer from a significant limitation: they ignore relationships that transcend the primary hierarchy.

In many real-world datasets, items share critical similarities regardless of their parent-child status. For instance, two countries might belong to different continents (hierarchy branches) but share a physical border, or two stocks might belong to different sectors but exhibit high price correlation. Traditional algorithms often "shuffle" cells during the area-optimization phase, destroying any initial similarity-based placement. Research indicates that in previous methods, up to 50% of geometric neighborhoods could be lost during the final steps of layout generation.

Methodology

To address the loss of neighborhood relationships, the authors propose a three-stage pipeline that maintains similarity constraints from initialization through the final rendering.

1. Preprocessing and Similarity Propagation

The process begins by aggregating similarity attributes (such as word embeddings or geographic coordinates) from leaf nodes up to their parents. This "upward aggregation" ensures that if two child nodes are constrained to be neighbors, their respective parent nodes are also encouraged to share a border. To maintain computational feasibility, a "binning and filtering" approach is used to extract only the most critical similarity constraints.

2. Geometric Initialization

Rather than relying on random placement, the algorithm employs dimensionality reduction techniques—such as Multi-Dimensional Scaling (MDS) or t-SNE—to project nodes into a 2D space based on their similarity. To map these projections onto the Voronoi grid, the algorithm uses Kuhn–Munkres matching to snap points to cells, followed by a greedy swapping phase to further refine neighborhood alignment.

3. Neighborhood-Preserving Optimization

The core innovation lies in the optimization phase. Standard Voronoi treemaps use Lloyd’s relaxation to move points toward the center of their cells to achieve desired area weights. The authors augment this process with an attraction force. If two nodes are designated as similar but do not share a boundary, the algorithm exerts a force to pull them together during the relaxation cycles. This prevents the "shuffling" effect common in traditional layouts.

4. Visual Encoding: The Interlocking Metaphor

To make these realized similarities explicit to the user, the algorithm employs a unique visual encoding. Edges between nodes that successfully satisfy a similarity constraint are rendered with an "interlocking" puzzle-piece pattern, while standard hierarchical boundaries remain straight.

Evaluation and Results

The method was evaluated across several diverse datasets, including geographic population data, Cifar-10 image categories (grouped by language embeddings), and SP500 stock correlations.

The effectiveness of the algorithm was measured by the percentage of similarity constraints realized as shared cell edges. In the "Country Population" dataset, the proposed method achieved a 83.33% preservation rate. This represents a substantial improvement over traditional random initialization (27.77%) and simple projection-based methods without force-based optimization (61.11%). Qualitative results demonstrate that the algorithm successfully places disparate branches—such as Russia and China in a specific geographic hierarchy—adjacent to one another, reflecting their real-world proximity.

Discussion and Limitations

A key insight of this research is that initialization alone is insufficient for neighborhood preservation; active forces must be maintained during the area-adjustment phase. However, the method faces challenges regarding computational complexity. The Munkres algorithm and iterative optimization result in a complexity of approximately $O(d \cdot n^3)$, where $d$ is the tree depth and $n$ is the number of nodes. This may limit the approach to datasets with a few hundred nodes.

Furthermore, the constraints of 2D planar embedding mean that not all similarity relationships can be satisfied simultaneously—an NP-hard problem. The algorithm is most effective for hierarchies with two to three levels; as trees deepen, the geometric restriction of a node remaining within its parent's cell makes it harder to satisfy constraints with distant branches.

Conclusion

Neighborhood-Preserving Voronoi Treemaps bridge the gap between hierarchical structure and relational similarity. By treating neighborhood preservation as a first-class citizen throughout the optimization process, the algorithm creates layouts where geometric proximity carries genuine semantic meaning, offering a more holistic view of complex datasets.

Summary updated

Abstract

Voronoi treemaps are used to depict nodes and their hierarchical relationships simultaneously. However, in addition to the hierarchical structure, data attributes, such as co-occurring features or similarities, frequently exist. Examples include geographical attributes like shared borders between countries or contextualized semantic information such as embedding vectors derived from large language models. In this work, we introduce a Voronoi treemap algorithm that leverages data similarity to generate neighborhood-preserving treemaps. First, we extend the treemap layout pipeline to consider similarity during data preprocessing. We then use a Kuhn-Munkres matching of similarities to centroidal Voronoi tessellation (CVT) cells to create initial Voronoi diagrams with equal cell sizes for each level. Greedy swapping is used to improve the neighborhoods of cells to match the data's similarity further. During optimization, cell areas are iteratively adjusted to their respective sizes while preserving the existing neighborhoods. We demonstrate the practicality of our approach through multiple real-world examples drawn from infographics and linguistics. To quantitatively assess the resulting treemaps, we employ treemap metrics and measure neighborhood preservation.
BibTeX
@article{paetzold2026neighborhood,
  author = {Patrick Paetzold and Rebecca Kehlbeck and Yumeng Xue and Bin Chen and Yunhai Wang and Oliver Deußen},
  title = {{Neighborhood-Preserving Voronoi Treemaps}},
  journal = {IEEE Trans. Vis. Comput. Graph.},
  year = {2026},
  doi = {10.1109/tvcg.2025.3633905},
}
Figure