ClusterSets : Optimizing Planar Clusters in Categorical Point Data

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

GEIGER, Jakob, Sabine CORNELSEN, Jan-Henrik HAUNERT, Philipp KINDERMANN, Tamara MCHEDLIDZE, Martin NÖLLENBURG, Yoshio OKAMOTO, Alexander WOLFF, 2021. ClusterSets : Optimizing Planar Clusters in Categorical Point Data. In: Computer Graphics Forum. Wiley. 40(3), pp. 471-481. ISSN 0167-7055. eISSN 1467-8659. Available under: doi: 10.1111/cgf.14322

@article{Geiger2021Clust-54375, title={ClusterSets : Optimizing Planar Clusters in Categorical Point Data}, year={2021}, doi={10.1111/cgf.14322}, number={3}, volume={40}, issn={0167-7055}, journal={Computer Graphics Forum}, pages={471--481}, author={Geiger, Jakob and Cornelsen, Sabine and Haunert, Jan-Henrik and Kindermann, Philipp and Mchedlidze, Tamara and Nöllenburg, Martin and Okamoto, Yoshio and Wolff, Alexander} }

Mchedlidze, Tamara 2021-07-21T08:19:29Z Wolff, Alexander Cornelsen, Sabine Cornelsen, Sabine 2021-07-21T08:19:29Z Mchedlidze, Tamara Geiger, Jakob Nöllenburg, Martin eng Kindermann, Philipp Nöllenburg, Martin 2021 Kindermann, Philipp In geographic data analysis, one is often given point data of different categories (such as facilities of a university categorized by department). Drawing upon recent research on set visualization, we want to visualize category membership by connecting points of the same category with visual links. Existing approaches that follow this path usually insist on connecting all members of a category, which may lead to many crossings and visual clutter. We propose an approach that avoids crossings between connections of different categories completely. Instead of connecting all data points of the same category, we subdivide categories into smaller, local clusters where needed. We do a case study comparing the legibility of drawings produced by our approach and those by existing approaches.<br /><br />In our problem formulation, we are additionally given a graph G on the data points whose edges express some sort of proximity. Our aim is to find a subgraph G′ of G with the following properties: (i) edges connect only data points of the same category, (ii) no two edges cross, and (iii) the number of connected components (clusters) is minimized. We then visualize the clusters in G′. For arbitrary graphs, the resulting optimization problem, Cluster Minimization, is NP-hard (even to approximate). Therefore, we introduce two heuristics. We do an extensive benchmark test on real-world data. Comparisons with exact solutions indicate that our heuristics do astonishing well for certain relative-neighborhood graphs. Okamoto, Yoshio Wolff, Alexander Geiger, Jakob Okamoto, Yoshio Haunert, Jan-Henrik Haunert, Jan-Henrik ClusterSets : Optimizing Planar Clusters in Categorical Point Data

This item appears in the following Collection(s)

Search KOPS


My Account