DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2024.24

Optimizing Symbol Visibility Through Displacement

Authors: Bernd Gärtner, Vishwas Kalani, Meghana M. Reddy, Wouter Meulemans, Bettina Speckmann, and Miloš Stojaković

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

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.

Cite as

Bernd Gärtner, Vishwas Kalani, Meghana M. Reddy, Wouter Meulemans, Bettina Speckmann, and Miloš Stojaković. Optimizing Symbol Visibility Through Displacement. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.SWAT.2024.24,
  author =	{G\"{a}rtner, Bernd and Kalani, Vishwas and M. Reddy, Meghana and Meulemans, Wouter and Speckmann, Bettina and Stojakovi\'{c}, Milo\v{s}},
  title =	{{Optimizing Symbol Visibility Through Displacement}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.24},
  URN =		{urn:nbn:de:0030-drops-200643},
  doi =		{10.4230/LIPIcs.SWAT.2024.24},
  annote =	{Keywords: symbol placement, visibility, jittering, stacking order}
}

Document

DOI: 10.4230/LIPIcs.FUN.2024.2

Poset Positional Games

Authors: Guillaume Bagan, Eric Duchêne, Florian Galliot, Valentin Gledel, Mirjana Mikalački, Nacim Oijid, Aline Parreau, and Miloš Stojaković

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset positional games, which are positional games with an additional structure - a poset on the elements of the board. Throughout the game play, based on this poset and the set of the board elements that are claimed up to that point, we reduce the set of available moves for the player whose turn it is - an element of the board can only be claimed if all the smaller elements in the poset are already claimed. We proceed to analyze these games in more detail, with a prime focus on the most studied convention, the Maker-Breaker games. First we build a general framework around poset positional games. Then, we perform a comprehensive study of the complexity of determining the game outcome, conditioned on the structure of the family of winning sets on the one side and the structure of the poset on the other.

Cite as

Guillaume Bagan, Eric Duchêne, Florian Galliot, Valentin Gledel, Mirjana Mikalački, Nacim Oijid, Aline Parreau, and Miloš Stojaković. Poset Positional Games. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bagan_et_al:LIPIcs.FUN.2024.2,
  author =	{Bagan, Guillaume and Duch\^{e}ne, Eric and Galliot, Florian and Gledel, Valentin and Mikala\v{c}ki, Mirjana and Oijid, Nacim and Parreau, Aline and Stojakovi\'{c}, Milo\v{s}},
  title =	{{Poset Positional Games}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.2},
  URN =		{urn:nbn:de:0030-drops-199100},
  doi =		{10.4230/LIPIcs.FUN.2024.2},
  annote =	{Keywords: Positional games, Maker-Breaker games, Game complexity, Poset, Connect 4}
}

Search Results

Documents authored by Stojaković, Miloš

Optimizing Symbol Visibility Through Displacement

Abstract

Cite as

Poset Positional Games

Abstract

Cite as

Thanks for your feedback!

Could not send message