ClusterSets: Optimizing Planar Clusters in Categorical Point Data

Simple item page
dc.contributor.authorGeiger, Jakoben_US
dc.contributor.authorCornelsen, Sabineen_US
dc.contributor.authorHaunert, Jan-Henriken_US
dc.contributor.authorKindermann, Philippen_US
dc.contributor.authorMchedlidze, Tamaraen_US
dc.contributor.authorNöllenburg, Martinen_US
dc.contributor.authorOkamoto, Yoshioen_US
dc.contributor.authorWolff, Alexanderen_US
dc.contributor.editorBorgo, Rita and Marai, G. Elisabeta and Landesberger, Tatiana vonen_US
dc.date.accessioned2021-06-12T11:02:38Z
dc.date.available2021-06-12T11:02:38Z
dc.date.issued2021
dc.description.abstractIn 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. 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 G0 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 G0. 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.en_US
dc.description.number3
dc.description.sectionheadersDesign Guidelines
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume40
dc.identifier.doi10.1111/cgf.14322
dc.identifier.issn1467-8659
dc.identifier.pages471-481
dc.identifier.urihttps://doi.org/10.1111/cgf.14322
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf14322
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.titleClusterSets: Optimizing Planar Clusters in Categorical Point Dataen_US
Files
Original bundle
Now showing 1 - 3 of 3
Thumbnail Image
Name:
v40i3pp471-481.pdf
Size:
10.86 MB
Format:
Adobe Portable Document Format
Download
Thumbnail Image
Name:
1261-file1.pdf
Size:
1.32 MB
Format:
Adobe Portable Document Format
Download
Thumbnail Image
Name:
cgf40-3_14322_ProjektDeal.pdf
Size:
11.08 MB
Format:
Adobe Portable Document Format
Description:
Projekt Deal version
Download
Collections
40-Issue 3