2026-07-25T06:36:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20064 2024-05-31T13:11:11Z ddc:004 open_access

Optimizing Symbol Visibility Through Displacement Gärtner, Bernd Kalani, Vishwas M. Reddy, Meghana Meulemans, Wouter Speckmann, Bettina Stojaković, Miloš symbol placement visibility jittering stacking order In information visualization, the position of symbols often encodes associated data values. When visualizing data elements with both a numerical and a categorical dimension, positioning in the categorical axis admits some flexibility. This flexibility can be exploited to reduce symbol overlap, and thereby increase legibility. In this paper we initialize the algorithmic study of optimizing symbol legibility via a limited displacement of the symbols. Specifically, we consider unit square symbols that need to be placed at specified y-coordinates. We optimize the drawing order of the symbols as well as their x-displacement, constrained within a rectangular container, to maximize the minimum visible perimeter over all squares. If the container has width and height at most 2, there is a point that stabs all squares. In this case, we prove that a staircase layout is arbitrarily close to optimality and can be computed in O(nlog n) time. If the width is at most 2, there is a vertical line that stabs all squares, and in this case, we give a 2-approximation algorithm (assuming fixed container height) that runs in O(nlog n) time. As a minimum visible perimeter of 2 is always trivially achievable, we measure this approximation with respect to the visible perimeter exceeding 2. We show that, despite its simplicity, the algorithm gives asymptotically optimal results for certain instances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bernd Gärtner and Vishwas Kalani and Meghana M. Reddy and Wouter Meulemans and Bettina Speckmann and Miloš Stojaković 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.24 urn:nbn:de:0030-drops-200643 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.24 eng https://creativecommons.org/licenses/by/4.0/legalcode