3 Search Results for "Castermans, Thom"

Document
DOI: 10.4230/LIPIcs.GD.2025.40
An Algorithm for Accurate and Simple-Looking Metaphorical Maps

Authors: Eleni Katsanou, Tamara Mchedlidze, Antonios Symvonis, and Thanos Tolias

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Metaphorical maps or contact representations are visual representations of vertex-weighted graphs that rely on the geographic map metaphor. The vertices are represented by countries, the weights by the areas of the countries, and the edges by contacts/boundaries among them. The accuracy with which the weights are mapped to areas and the simplicity of the polygons representing the countries are the two classical optimization goals for metaphorical maps. Mchedlidze & Schnorr [Mchedlidze and Schnorr, 2022] presented a force-based algorithm that creates metaphorical maps that balance between these two optimization goals. Their maps look visually simple, but the accuracy of the maps is far from optimal - the countries' areas can vary up to 30% compared to required. In this paper, we provide a multi-fold extension of the algorithm in [Mchedlidze and Schnorr, 2022]. More specifically: 1) Towards improving accuracy: We introduce the notion of region stiffness and suggest a technique for varying the stiffness based on the current pressure of map regions. 2) Towards maintaining simplicity: We introduce a weight coefficient to the pressure force exerted on each polygon point based on whether the corresponding point appears along a narrow passage. 3) Towards generality: We cover, in contrast to [Mchedlidze and Schnorr, 2022], non-triangulated graphs. This is done by either generating points where more than three regions meet or by introducing holes in the metaphorical map. We perform an extended experimental evaluation that, among other results, reveals that our algorithm is able to construct metaphorical maps with nearly perfect area accuracy with a little sacrifice in their simplicity.
Cite as

Eleni Katsanou, Tamara Mchedlidze, Antonios Symvonis, and Thanos Tolias. An Algorithm for Accurate and Simple-Looking Metaphorical Maps. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{katsanou_et_al:LIPIcs.GD.2025.40,
  author =	{Katsanou, Eleni and Mchedlidze, Tamara and Symvonis, Antonios and Tolias, Thanos},
  title =	{{An Algorithm for Accurate and Simple-Looking Metaphorical Maps}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.40},
  URN =		{urn:nbn:de:0030-drops-250268},
  doi =		{10.4230/LIPIcs.GD.2025.40},
  annote =	{Keywords: Metaphorical maps, contact representation, accuracy (cartographic error), simplicity (polygon complexity), force directed algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.49
Competitive Searching for a Line on a Line Arrangement

Authors: Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We discuss the problem of searching for an unknown line on a known or unknown line arrangement by a searcher S, and show that a search strategy exists that finds the line competitively, that is, with detour factor at most a constant when compared to the situation where S has all knowledge. In the case where S knows all lines but not which one is sought, the strategy is 79-competitive. We also show that it may be necessary to travel on Omega(n) lines to realize a constant competitive ratio. In the case where initially, S does not know any line, but learns about the ones it encounters during the search, we give a 414.2-competitive search strategy.
Cite as

Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans. Competitive Searching for a Line on a Line Arrangement. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 49:1-49:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bouts_et_al:LIPIcs.ISAAC.2018.49,
  author =	{Bouts, Quirijn and Castermans, Thom and van Goethem, Arthur and van Kreveld, Marc and Meulemans, Wouter},
  title =	{{Competitive Searching for a Line on a Line Arrangement}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{49:1--49:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.49},
  URN =		{urn:nbn:de:0030-drops-99970},
  doi =		{10.4230/LIPIcs.ISAAC.2018.49},
  annote =	{Keywords: Competitive searching, line arrangement, detour factor, search strategy}
}
Document
Multimedia Contribution
DOI: 10.4230/LIPIcs.SoCG.2017.63
Ruler of the Plane - Games of Geometry (Multimedia Contribution)

Authors: Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Ruler of the Plane is a set of games illustrating concepts from combinatorial and computational geometry. The games are based on the art gallery problem, ham-sandwich cuts, the Voronoi game, and geometric network connectivity problems like the Euclidean minimum spanning tree and traveling salesperson problem.
Cite as

Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke. Ruler of the Plane - Games of Geometry (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 63:1-63:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{beekhuis_et_al:LIPIcs.SoCG.2017.63,
  author =	{Beekhuis, Sander and Buchin, Kevin and Castermans, Thom and Hurks, Thom and Sonke, Willem},
  title =	{{Ruler of the Plane - Games of Geometry}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{63:1--63:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.63},
  URN =		{urn:nbn:de:0030-drops-72400},
  doi =		{10.4230/LIPIcs.SoCG.2017.63},
  annote =	{Keywords: art gallery problem, ham-sandwich cuts, Voronoi game, traveling sales-person problem}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018
  • 1 2017

  • Refine by Author
  • 2 Castermans, Thom
  • 1 Beekhuis, Sander
  • 1 Bouts, Quirijn
  • 1 Buchin, Kevin
  • 1 Hurks, Thom
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Competitive searching
  • 1 Metaphorical maps
  • 1 Voronoi game
  • 1 accuracy (cartographic error)
  • 1 art gallery problem
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact