24 Search Results for "Polishchuk, Valentin"

Document
DOI: 10.4230/LIPIcs.GD.2025.17
Visualizing Treewidth

Authors: Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg

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

Abstract
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.
Cite as

Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg. Visualizing Treewidth. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.GD.2025.17,
  author =	{Chiu, Alvin and Depian, Thomas and Eppstein, David and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Visualizing Treewidth}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{17:1--17:20},
  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.17},
  URN =		{urn:nbn:de:0030-drops-250034},
  doi =		{10.4230/LIPIcs.GD.2025.17},
  annote =	{Keywords: Graph drawing, witness drawings, pathwidth, treewidth}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.39
Optimizing Wiggle in Storylines

Authors: Alexander Dobler, Tim Hegemann, Martin Nöllenburg, and Alexander Wolff

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

Abstract
A storyline visualization shows interactions between characters over time. Each character is represented by an x-monotone curve. Time is mapped to the x-axis, and groups of characters that interact at a particular point t in time must be ordered consecutively in the y-dimension at x = t. The predominant objective in storyline optimization so far has been the minimization of crossings between (blocks of) characters. Building on this work, we investigate another important, but less studied quality criterion, namely the minimization of wiggle, i.e., the amount of vertical movement of the characters over time. Given a storyline instance together with an ordering of the characters at any point in time, we show that wiggle count minimization is NP-complete. In contrast, we provide algorithms based on mathematical programming to solve linear wiggle height minimization and quadratic wiggle height minimization efficiently. Finally, we introduce a new method for routing character curves that focuses on keeping distances between neighboring curves constant as long as they run in parallel. We have implemented our algorithms, and we conduct a case study that explores the differences between the three optimization objectives. We use existing benchmark data, but we also present a new use case for storylines, namely the visualization of rolling stock schedules in railway operation.
Cite as

Alexander Dobler, Tim Hegemann, Martin Nöllenburg, and Alexander Wolff. Optimizing Wiggle in Storylines. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.GD.2025.39,
  author =	{Dobler, Alexander and Hegemann, Tim and N\"{o}llenburg, Martin and Wolff, Alexander},
  title =	{{Optimizing Wiggle in Storylines}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{39:1--39: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.39},
  URN =		{urn:nbn:de:0030-drops-250252},
  doi =		{10.4230/LIPIcs.GD.2025.39},
  annote =	{Keywords: Storyline visualization, wiggle minimization, NP-complete, linear programming, quadratic programming, experimental analysis}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.2
Covering Simple Orthogonal Polygons with Rectangles

Authors: Aniket Basu Roy

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study the problem of Covering Orthogonal Polygons with Rectangles, focusing on three variants: covering the interior, the boundary, and the corners. While previous work provided constant-factor approximation algorithms for these problems, significant improvements had not been achieved for over two decades. The main contribution of this work is the development of a Polynomial Time Approximation Scheme (PTAS) for both the Boundary Cover and Corner Cover problems on simple polygons, using a local search algorithm. Our work advances the state of the art, improving upon the previous best-known 4-approximation for the Boundary Cover and 2-approximation for the Corner Cover problems. The technical core of our work lies in proving the existence of planar support graphs for certain geometric hypergraphs defined by the polygon and its containment-maximal rectangles. This structural insight enables the application of the local search framework to achieve the PTAS results. We also demonstrate the limitations of this approach by constructing instances where local search fails for the Interior Cover and certain dual problems, such as the Maximum Antirectangle and Hitting Set problems. Additionally, the methods yield a PTAS for a special case of the Discrete Independent Set problem for rectangles. These results not only settle longstanding open questions but also introduce new techniques that may be of independent interest within computational geometry.
Cite as

Aniket Basu Roy. Covering Simple Orthogonal Polygons with Rectangles. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{basuroy:LIPIcs.APPROX/RANDOM.2025.2,
  author =	{Basu Roy, Aniket},
  title =	{{Covering Simple Orthogonal Polygons with Rectangles}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.2},
  URN =		{urn:nbn:de:0030-drops-243686},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.2},
  annote =	{Keywords: Polygon Covering, Approximation Algorithms, Orthogonal Polygons, Rectangles, Local Search, Planar Supports}
}
Artifact
Software
DOI: 10.4230/artifacts.24586
Polygon sweeping with line of sight between covisible agents

Authors: Kien C. Huynh

Abstract
Cite as

Kien C. Huynh. Polygon sweeping with line of sight between covisible agents (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{coderepo,
   title = {{Polygon sweeping with line of sight between covisible agents}}, 
   author = {Huynh, Kien C.},
   note = {Software (visited on 2025-08-29)},
   url = {https://github.com/KienHuynh/polygon_sweeping},
   doi = {10.4230/artifacts.24586},
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.6
Vantage Point Selection Algorithms for Bottleneck Capacity Estimation

Authors: Vikrant Ashvinkumar, Rezaul Chowdhury, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Motivated by the problem of estimating bottleneck capacities on the Internet, we formulate and study the problem of vantage point selection. We are given a graph G = (V, E) whose edges E have unknown capacity values that are to be discovered. Probes from a vantage point, i.e, a vertex v ∈ V, along shortest paths from v to all other vertices, reveal bottleneck edge capacities along each path. Our goal is to select k vantage points from V that reveal the maximum number of bottleneck edge capacities. We consider both a non-adaptive setting where all k vantage points are selected before any bottleneck capacity is revealed, and an adaptive setting where each vantage point selection instantly reveals bottleneck capacities along all shortest paths starting from that point. In the non-adaptive setting, by considering a relaxed model where edge capacities are drawn from a random permutation (which still leaves the problem of maximizing the expected number of revealed edges NP-hard), we are able to give a 1-1/e approximate algorithm. In the adaptive setting we work with the least permissive model where edge capacities are arbitrarily fixed but unknown. We compare with the best solution for the particular input instance (i.e. by enumerating all choices of k tuples), and provide both lower bounds on instance optimal approximation algorithms and upper bounds for trees and planar graphs.
Cite as

Vikrant Ashvinkumar, Rezaul Chowdhury, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk. Vantage Point Selection Algorithms for Bottleneck Capacity Estimation. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ashvinkumar_et_al:LIPIcs.WADS.2025.6,
  author =	{Ashvinkumar, Vikrant and Chowdhury, Rezaul and Gao, Jie and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{Vantage Point Selection Algorithms for Bottleneck Capacity Estimation}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.6},
  URN =		{urn:nbn:de:0030-drops-242376},
  doi =		{10.4230/LIPIcs.WADS.2025.6},
  annote =	{Keywords: Bottleneck capacity, Approximation algorithms, Instance optimality}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.39
Sweeping a Domain with Line-Of-Sight Between Covisible Agents

Authors: Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We consider sweeping a polygonal domain using variable-length segments whose endpoints can be considered to be mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to one of the segments. The objective is to sweep the domain as quickly as possible. We show that the problem is NP-hard even in simple polygons and even for a single segment (two agents), and give constant-factor approximation algorithms, both for simple polygons and polygons with holes. Our approximations are obtained by introducing a new type of "window partition" of the polygon, which may find other applications. For domains with holes, our results are based on a non-trivial topological argument proving a surprising fact: a connected subset of the domain, whose points are swept but not directly touched by the agents, may contain at most one hole.
Cite as

Kien C. Huynh, Joseph S. B. Mitchell, and Valentin Polishchuk. Sweeping a Domain with Line-Of-Sight Between Covisible Agents. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 39:1-39:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huynh_et_al:LIPIcs.WADS.2025.39,
  author =	{Huynh, Kien C. and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{Sweeping a Domain with Line-Of-Sight Between Covisible Agents}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{39:1--39:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.39},
  URN =		{urn:nbn:de:0030-drops-242706},
  doi =		{10.4230/LIPIcs.WADS.2025.39},
  annote =	{Keywords: Polygon sweeping, collaborating agents, motion coordination, makespan optimization}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.34
Link Diameter, Radius and 2-Point Link Distance Queries in Polygonal Domains

Authors: Mart Hagedoorn and Valentin Polishchuk

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We show how to preprocess a polygonal domain with holes so that the link distance (the number of links in a minimum-link path) between two query points in the domain can be reported efficiently. Using our data structures, the link diameter of the domain (i.e., the maximum number of links that may be required in a minimum-link path between two points in the domain) as well as the link center and radius of the domain (i.e., the point minimizing the maximum link distance to the furthest point in the domain and this maximum link distance) can be found in polynomial time. We also give a simpler algorithm for finding the link diameter, not using the link distance query structures. Answering 2-point link distance queries and computing the link diameter/radius/center in polygonal domains have been open questions since these problems were studied for simple polygons in the 90’s.
Cite as

Mart Hagedoorn and Valentin Polishchuk. Link Diameter, Radius and 2-Point Link Distance Queries in Polygonal Domains. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hagedoorn_et_al:LIPIcs.WADS.2025.34,
  author =	{Hagedoorn, Mart and Polishchuk, Valentin},
  title =	{{Link Diameter, Radius and 2-Point Link Distance Queries in Polygonal Domains}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.34},
  URN =		{urn:nbn:de:0030-drops-242659},
  doi =		{10.4230/LIPIcs.WADS.2025.34},
  annote =	{Keywords: Minimum-link paths, link distance, diameter, center, radius, 2-point distance queries}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.36
Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.
Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}
Artifact
Software
DOI: 10.4230/artifacts.23018
RolfSvenning/ContiguousArtGallery

Authors: Rolf Svenning

Abstract
Cite as

Rolf Svenning. RolfSvenning/ContiguousArtGallery (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{github_impl,
   title = {{RolfSvenning/ContiguousArtGallery}}, 
   author = {Svenning, Rolf},
   note = {Software, Independent Research Fund Denmark (DFF), grant 9131- 00113B, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7;origin=https://github.com/RolfSvenning/ContiguousArtGallery;visit=swh:1:snp:24512c962bdc05c9bff737a006e263acf6b13e78;anchor=swh:1:rev:af66971aa2b832e98dcd6b1fcf8eac88d5901b93}{\texttt{swh:1:dir:7cfaba2c09d953feb90a49f0e26370ea3f7719a7}} (visited on 2025-06-20)},
   url = {https://github.com/RolfSvenning/ContiguousArtGallery},
   doi = {10.4230/artifacts.23018},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.20
Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems

Authors: Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.
Cite as

Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng. Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.20,
  author =	{Biniaz, Ahmad and Maheshwari, Anil and Merrild, Magnus Christian Ring and Mitchell, Joseph S. B. and Odak, Saeed and Polishchuk, Valentin and Robson, Eliot W. and Rysgaard, Casper Moldrup and Schou, Jens Kristian Refsgaard and Shermer, Thomas and Spalding-Jamieson, Jack and Svenning, Rolf and Zheng, Da Wei},
  title =	{{Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.20},
  URN =		{urn:nbn:de:0030-drops-231720},
  doi =		{10.4230/LIPIcs.SoCG.2025.20},
  annote =	{Keywords: Art Gallery Problem, Computational Geometry, Combinatorics, Discrete Algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.30
Fast, Fair and Truthful Distributed Stable Matching for Common Preferences

Authors: Juho Hirvonen and Sara Ranjbaran

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Stable matching is a fundamental problem studied both in economics and computer science. The task is to find a matching between two sides of agents that have preferences over who they want to be matched with. A matching is stable if no pair of agents prefer each other over their current matches. The deferred acceptance algorithm of Gale and Shapley solves this problem in polynomial time. Further, it is a mechanism: the proposing side in the algorithm is always incentivised to report their preferences truthfully. The deferred acceptance algorithm has a natural interpretation as a distributed algorithm (and thus a distributed mechanism). However, the algorithm is slow in the worst case and it is known that the stable matching problem cannot be solved efficiently in the distributed setting. In this work we study a natural special case of the stable matching problem where all agents on one of the two sides share common preferences. We show that in this case the deferred acceptance algorithm does yield a fast and truthful distributed mechanism for finding a stable matching. We show how algorithms for sampling random colorings can be used to break ties fairly and extend the results to fractional stable matching.
Cite as

Juho Hirvonen and Sara Ranjbaran. Fast, Fair and Truthful Distributed Stable Matching for Common Preferences. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hirvonen_et_al:LIPIcs.OPODIS.2024.30,
  author =	{Hirvonen, Juho and Ranjbaran, Sara},
  title =	{{Fast, Fair and Truthful Distributed Stable Matching for Common Preferences}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.30},
  URN =		{urn:nbn:de:0030-drops-225666},
  doi =		{10.4230/LIPIcs.OPODIS.2024.30},
  annote =	{Keywords: stable matching, deferred acceptance, local algorithm, mechanism design}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.27
Optimizing Visibility-Based Search in Polygonal Domains

Authors: Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, and Valentin Polishchuk

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

Abstract
Given a geometric domain P, visibility-based search problems seek routes for one or more mobile agents ("watchmen") to move within P in order to be able to see a portion (or all) of P, while optimizing objectives, such as the length(s) of the route(s), the size (e.g., area or volume) of the portion seen, the probability of detecting a target distributed within P according to a prior distribution, etc. The classic watchman route problem seeks a shortest route for an observer, with omnidirectional vision, to see all of P. In this paper we study bicriteria optimization problems for a single mobile agent within a polygonal domain P in the plane, with the criteria of route length and area seen. Specifically, we address the problem of computing a minimum length route that sees at least a specified area of P (minimum length, for a given area quota). We also study the problem of computing a length-constrained route that sees as much area as possible. We provide hardness results and approximation algorithms. In particular, for a simple polygon P we provide the first fully polynomial-time approximation scheme for the problem of computing a shortest route seeing an area quota, as well as a (slightly more efficient) polynomial dual approximation. We also consider polygonal domains P (with holes) and the special case of a planar domain consisting of a union of lines. Our results yield the first approximation algorithms for computing a time-optimal search route in P to guarantee some specified probability of detection of a static target within P, randomly distributed in P according to a given prior distribution.
Cite as

Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, and Valentin Polishchuk. Optimizing Visibility-Based Search in Polygonal Domains. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{huynh_et_al:LIPIcs.SWAT.2024.27,
  author =	{Huynh, Kien C. and Mitchell, Joseph S. B. and Nguyen, Linh and Polishchuk, Valentin},
  title =	{{Optimizing Visibility-Based Search in Polygonal Domains}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{27:1--27: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.27},
  URN =		{urn:nbn:de:0030-drops-200671},
  doi =		{10.4230/LIPIcs.SWAT.2024.27},
  annote =	{Keywords: Quota watchman route problem, budgeted watchman route problem, visibility-based search, approximation}
}
Document
Salon des Refusés
DOI: 10.4230/LIPIcs.FUN.2024.32
Eating Ice-Cream with a Colander

Authors: Kien Huynh and Valentin Polishchuk

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

Abstract
k-order α-hull is a generalization of both k-hull and α-shape (which are generalizations of convex hull); since its introduction in a 2014 IPL paper (which also established its combinatorial properties and gave efficient algorithms to compute it), it was used in a variety of applications (as witnessed by 38 citations in Google Scholar) ranging from computer graphics to hydrology to seismology. The subject must have been so rich and complex that it took more than a year to review the submission at IPL (which was chosen as the venue "Devoted to the Rapid Publication"), as may be witnessed by the timeline in the paper header. Nonetheless it was not rich enough to warrant publication at SODA 2009 and WADS 2009 (the reviews saying it is not yet ready for the prime time - cited from memory) nor in FUN 2010 to which the paper was submitted under the title "Eating Ice-Cream with Colander"
Cite as

Kien Huynh and Valentin Polishchuk. Eating Ice-Cream with a Colander. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 32:1-32:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{huynh_et_al:LIPIcs.FUN.2024.32,
  author =	{Huynh, Kien and Polishchuk, Valentin},
  title =	{{Eating Ice-Cream with a Colander}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{32:1--32:4},
  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.32},
  URN =		{urn:nbn:de:0030-drops-199408},
  doi =		{10.4230/LIPIcs.FUN.2024.32},
  annote =	{Keywords: computational geometry, alpha-shape, k-hull, robust shape reconstruction}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.51
On Flipping the Fréchet Distance

Authors: Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
The classical and extensively-studied Fréchet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over all concurrent positions of the two agents. In this article we investigate a "flipped" Fréchet measure defined by a sup min - the supremum is over all traversals of the curves, and the minimum is over all concurrent positions of the two agents. This measure produces a notion of "social distance" between two curves (or general domains), where agents traverse curves while trying to stay as far apart as possible. We first study the flipped Fréchet measure between two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. We then consider this measure on polygons, where it denotes the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon. We investigate several variants of the problem in this setting, for some of which we provide linear time algorithms. Finally, we consider this measure on graphs. We draw connections between our proposed flipped Fréchet measure and existing related work in computational geometry, hoping that our new measure may spawn investigations akin to those performed for the Fréchet distance, and into further interesting problems that arise.
Cite as

Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk. On Flipping the Fréchet Distance. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.ITCS.2023.51,
  author =	{Filtser, Omrit and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{On Flipping the Fr\'{e}chet Distance}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{51:1--51:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.51},
  URN =		{urn:nbn:de:0030-drops-175548},
  doi =		{10.4230/LIPIcs.ITCS.2023.51},
  annote =	{Keywords: curves, polygons, distancing measure}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.7
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

Authors: Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the "size" of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.
Cite as

Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth. Cutting Polygons into Small Pieces with Chords: Laser-Based Localization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.ESA.2020.7,
  author =	{Arkin, Esther M. and Das, Rathish and Gao, Jie and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin and T\'{o}th, Csaba D.},
  title =	{{Cutting Polygons into Small Pieces with Chords: Laser-Based Localization}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.7},
  URN =		{urn:nbn:de:0030-drops-128736},
  doi =		{10.4230/LIPIcs.ESA.2020.7},
  annote =	{Keywords: Polygon partition, Arrangements, Visibility, Localization}
}
  • Refine by Type
  • 22 Document/PDF
  • 9 Document/HTML
  • 2 Artifact

  • Refine by Publication Year
  • 11 2025
  • 2 2024
  • 1 2023
  • 2 2020
  • 2 2019
  • Show More...

  • Refine by Author
  • 16 Polishchuk, Valentin
  • 8 Mitchell, Joseph S. B.
  • 3 Goswami, Mayank
  • 3 Huynh, Kien C.
  • 2 Arkin, Esther M.
  • Show More...

  • Refine by Series/Journal
  • 21 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 11 Theory of computation → Computational geometry
  • 5 Theory of computation → Design and analysis of algorithms
  • 2 Human-centered computing → Graph drawings
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Combinatorial algorithms
  • Show More...

  • Refine by Keyword
  • 2 Visibility
  • 2 visibility
  • 1 2-point distance queries
  • 1 Air Traffic Management
  • 1 Approximation Algorithms
  • 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