59 Search Results for "Mitchell, Joseph S. B."

Document
DOI: 10.4230/LIPIcs.SoCG.2026.1
Covering and Partitioning Complex Objects with Small Pieces

Authors: Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We study the problems of covering or partitioning a polygon P (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contained in an axis-aligned unit square. For covering, we seek to write P as a union of small pieces, and in partitioning, we furthermore require the pieces to be pairwise interior-disjoint. We show that these problems are in fact equivalent: Optimum covers and partitions have the same number of pieces. For covering, a natural local search algorithm repeatedly attempts to replace k pieces from a candidate cover with k-1 pieces. In two dimensions and for sufficiently large k, we show that when no such swap is possible, the cover is a 1+ O(1/√k) approximation, hence obtaining the first PTAS for the problem. Prior to our work, the only known algorithm was a 13-approximation that only works for polygons without holes [Abrahamsen and Rasmussen, SODA 2025]. In contrast, in the three dimensional version of the problem, for a polyhedron P of complexity n, we show that it is NP-hard to approximate an optimal cover or partition to within a factor that is logarithmic in n, even if P is simple, i.e., has genus 0 and no holes.
Cite as

Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade. Covering and Partitioning Complex Objects with Small Pieces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.SoCG.2026.1,
  author =	{Aamand, Anders and Abrahamsen, Mikkel and Browne, Reilly and Goswami, Mayank and Kasthurirangan, Prahlad Narasimhan and Kleist, Linda and Mitchell, Joseph S. B. and Polishchuk, Valentin and Stade, Jack},
  title =	{{Covering and Partitioning Complex Objects with Small Pieces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.1},
  URN =		{urn:nbn:de:0030-drops-258077},
  doi =		{10.4230/LIPIcs.SoCG.2026.1},
  annote =	{Keywords: Covering, partitioning, polygon, small piece, PTAS}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.65
Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms

Authors: Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Roughgarden [Roughgarden, 2020] initiates the study of Transaction Fee Mechanisms (TFMs), and posits that the on-chain game of a "good" TFM should be on-chain simple (OnC-S), i.e., incentive compatible for both the users and the miner. Recent work of Ganesh, Thomas an Weinberg [Ganesh et al., 2024] posit that they should additionally be Off-Chain Influence-Proof (OffC-IP), which means that the miner cannot achieve any additional revenue by separately conducting an off-chain auction to determine on-chain inclusion. They observe that a cryptographic second-price auction satisfies both properties, but leave open the question of whether other mechanisms (such as those not dependent on cryptography) satisfy these properties. In this paper, we characterize OffC-IP TFMs: They are those satisfying a burn identity relating the burn rule to the allocation rule. In particular, we show that auction is OffC-IP if and only if its (induced direct-revelation) allocation rule X̄(⋅) and burn rule B̅(⋅) (both of which take as input users' values v₁, … , v_n) are truthful when viewing (X̄(⋅), B̅(⋅)) as the allocation and pricing rule of a multi-item auction for a single additive buyer with values (φ(v₁),…, φ(v_n)) equal to the users' virtual values. Building on this burn identity, we characterize OffC-IP and OnC-S TFMs that are deterministic and do not use cryptography: They are posted-price mechanisms with specially-tuned burns. As a corollary, we show that such TFMs can only exist with infinite supply and prior-dependence. However, we show that for randomized TFMs, there are additional OnC-S and OffC-IP auctions that do not use cryptography (even when there is {finite} supply, under prior-dependence with a bounded prior distribution). Holistically, our results show that while OffC-IP is a fairly stringent requirement, families of OffC-IP mechanisms can be found for a variety of settings.
Cite as

Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg. Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 65:1-65:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ITCS.2026.65,
  author =	{Ganesh, Aadityan and Thomas, Clayton and Weinberg, S. Matthew},
  title =	{{Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{65:1--65:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.65},
  URN =		{urn:nbn:de:0030-drops-253527},
  doi =		{10.4230/LIPIcs.ITCS.2026.65},
  annote =	{Keywords: Transaction Fee Mechanism Design, Off-Chain Influence Proofness, Blockchain, Decentralized Finance, Simple Auctions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.94
Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Authors: Yingxi Li, Ellen Vitercik, and Mingwei Yang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In the online metric matching problem, n servers and n requests lie in a metric space. Servers are available upfront, and requests arrive sequentially. An arriving request must be matched immediately and irrevocably to an available server, incurring a cost equal to their distance. The goal is to minimize the total matching cost. We study this problem in [0, 1]^d with the Euclidean metric, when servers are adversarial and requests are independently drawn from distinct distributions that satisfy a mild smoothness condition. Our main result is an O(1)-competitive algorithm for d ≠ 2 that requires no distributional knowledge, relying only on a single sample from each request distribution. To our knowledge, this is the first algorithm to achieve an o(log n) competitive ratio for non-trivial metrics beyond the i.i.d. setting. Our approach bypasses the Ω(log n) barrier introduced by probabilistic metric embeddings: instead of analyzing the embedding distortion and the algorithm separately, we directly bound the cost of the algorithm on the target metric space of a simple deterministic embedding. We then combine this analysis with lower bounds on the offline optimum for Euclidean metrics, derived via majorization arguments, to obtain our guarantees.
Cite as

Yingxi Li, Ellen Vitercik, and Mingwei Yang. Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 94:1-94:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2026.94,
  author =	{Li, Yingxi and Vitercik, Ellen and Yang, Mingwei},
  title =	{{Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{94:1--94:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.94},
  URN =		{urn:nbn:de:0030-drops-253815},
  doi =		{10.4230/LIPIcs.ITCS.2026.94},
  annote =	{Keywords: Online algorithm, Metric matching, Competitive analysis, Smoothed analysis}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.6
A Dimension-Reducing Fréchet Simplification Oracle

Authors: Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let P be a polygonal curve with n vertices in the plane. We construct a data structure of size O(n log n) suited for simplification queries of the following kind. Given a query line 𝓁 and an integer k ≥ 1, find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to P, among all such curves. Using our data structure, a query can be handled in O(k² log³ n + k log⁴n) time. More generally, a geometric tree T on n vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair u, v of its vertices, a line 𝓁, and an integer k ≥ 1, one can find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to the path from u to v in T, in time O(k² polylog n). For the general dimension-reduction problem, where P is a curve in ℝ^d (d ≥ 3), 0 < ε₀ < 1 is a real parameter, and a query specifies a g-flat h (1 ≤ g ≤ d-1) and an integer k ≥ 1, we construct a data structure of size O(nlog n + f(ε₀) n), where f(ε₀) = (1+1/ε₀)^{(d-1)/2}, that allows us to find a curve Q on h with at most k vertices, whose discrete Fréchet distance to P is at most 1+ε₀ times the distance of Q^* to P, where Q^* is such a curve that minimizes the distance to P. The query handling time is O(f(ε₀) k² log² n).
Cite as

Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. A Dimension-Reducing Fréchet Simplification Oracle. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2025.6,
  author =	{Aronov, Boris and Farhana, Tsuri and Katz, Matthew J. and Ramesh, Indu},
  title =	{{A Dimension-Reducing Fr\'{e}chet Simplification Oracle}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.6},
  URN =		{urn:nbn:de:0030-drops-249149},
  doi =		{10.4230/LIPIcs.ISAAC.2025.6},
  annote =	{Keywords: Computational geometry, discrete Fr\'{e}chet distance, curve simplification oracle, restricted minimum enclosing disk queries}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.46
Realizing Metric Spaces with Convex Obstacles

Authors: Sándor Kisfaludi-Bak and Leonidas Theocharous

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The presence of obstacles has a significant impact on distance computation, motion-planning, and visibility. These problems have been studied extensively in the planar setting, while our understanding of these problems in 3- and higher-dimensional spaces is still rudimentary. In this paper, we study the impact of different types of obstacles on the induced geodesic metric in 3-dimensional Euclidean space. We say that a finite metric space (X, dist_X) is approximately realizable by a collection 𝒯 of obstacles in ℝ³ if for any ε > 0 it can be embedded into (ℝ³⧵⋃_{T∈𝒯} T, dist_𝒯) with worst-case multiplicative distortion 1+ε, where dist_𝒯 denotes the geodesic distance in the free space induced by 𝒯. We focus on three key geometric properties of obstacles -convexity, disjointness, and fatness- and examine how dropping each one of them affects the existence of such embeddings. Our main result concerns dropping the fatness property: we demonstrate that any finite metric space is realizable with 1+ε worst-case multiplicative distortion using a collection of convex and pairwise disjoint obstacles in ℝ³, even if the obstacles are congruent and equilateral triangles. Based on the same construction, we can also show that if we require fatness but drop any of the other two properties instead, then we can still approximately realize any finite metric space. Our results have important implications on the approximability of tsp with obstacles, a natural variant of tsp introduced recently by Alkema et al. (ESA 2022). Specifically, we use the recent results of Banerjee et al. on tsp in doubling spaces (FOCS 2024) and of Chew et al. on distances among obstacles (Inf. Process. Lett. 2002) to show that tsp with obstacles admits a PTAS if the obstacles are convex, fat, and pairwise disjoint. If any of these three properties is dropped, then our results, combined with the APX-hardness of Metric tsp, demonstrate that tsp with obstacles is APX-hard.
Cite as

Sándor Kisfaludi-Bak and Leonidas Theocharous. Realizing Metric Spaces with Convex Obstacles. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 46:1-46:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.ISAAC.2025.46,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Theocharous, Leonidas},
  title =	{{Realizing Metric Spaces with Convex Obstacles}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{46:1--46:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.46},
  URN =		{urn:nbn:de:0030-drops-249545},
  doi =		{10.4230/LIPIcs.ISAAC.2025.46},
  annote =	{Keywords: traveling salesman, geodesic distance}
}
Document
Survey
DOI: 10.4230/TGDK.3.2.1
Resilience in Knowledge Graph Embeddings

Authors: Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo

Published in: TGDK, Volume 3, Issue 2 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 2

Abstract
In recent years, knowledge graphs have gained interest and witnessed widespread applications in various domains, such as information retrieval, question-answering, recommendation systems, amongst others. Large-scale knowledge graphs to this end have demonstrated their utility in effectively representing structured knowledge. To further facilitate the application of machine learning techniques, knowledge graph embedding models have been developed. Such models can transform entities and relationships within knowledge graphs into vectors. However, these embedding models often face challenges related to noise, missing information, distribution shift, adversarial attacks, etc. This can lead to sub-optimal embeddings and incorrect inferences, thereby negatively impacting downstream applications. While the existing literature has focused so far on adversarial attacks on KGE models, the challenges related to the other critical aspects remain unexplored. In this paper, we, first of all, give a unified definition of resilience, encompassing several factors such as generalisation, in-distribution generalization, distribution adaption, and robustness. After formalizing these concepts for machine learning in general, we define them in the context of knowledge graphs. To find the gap in the existing works on resilience in the context of knowledge graphs, we perform a systematic survey, taking into account all these aspects mentioned previously. Our survey results show that most of the existing works focus on a specific aspect of resilience, namely robustness. After categorizing such works based on their respective aspects of resilience, we discuss the challenges and future research directions.
Cite as

Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo. Resilience in Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 2, pp. 1:1-1:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{sharma_et_al:TGDK.3.2.1,
  author =	{Sharma, Arnab and Kouagou, N'Dah Jean and Ngomo, Axel-Cyrille Ngonga},
  title =	{{Resilience in Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:38},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.2.1},
  URN =		{urn:nbn:de:0030-drops-248117},
  doi =		{10.4230/TGDK.3.2.1},
  annote =	{Keywords: Knowledge graphs, Resilience, Robustness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.75
An Improved Bound for Plane Covering Paths

Authors: Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, and Leonidas Theocharous

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A covering path for a finite set P of points in the plane is a polygonal path such that every point of P lies on a segment of the path. The vertices of the path need not be at points of P. A covering path is plane if its segments do not cross each other. Let π(n) be the minimum number such that every set of n points in the plane admits a plane covering path with at most π(n) segments. We prove that π(n) ≤ ⌈6n/7⌉. This improves the previous best-known upper bound of ⌈21n/22⌉, due to Biniaz (SoCG 2023). Our proof is constructive and yields a simple O(n log n)-time algorithm for computing a plane covering path.
Cite as

Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, and Leonidas Theocharous. An Improved Bound for Plane Covering Paths. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 75:1-75:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2025.75,
  author =	{A. Akitaya, Hugo and Aloupis, Greg and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Gavoille, Cyril and Iacono, John and Kleist, Linda and Smid, Michiel and Souvaine, Diane and Theocharous, Leonidas},
  title =	{{An Improved Bound for Plane Covering Paths}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{75:1--75:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.75},
  URN =		{urn:nbn:de:0030-drops-245432},
  doi =		{10.4230/LIPIcs.ESA.2025.75},
  annote =	{Keywords: Covering Path, Upper Bound, Simple Algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.58
Streaming Diameter of High-Dimensional Points

Authors: Magnús M. Halldórsson, Nicolaos Matsakis, and Pavel Veselý

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We improve the space bound for streaming approximation of Diameter but also of Farthest Neighbor queries, Minimum Enclosing Ball and its Coreset, in high-dimensional Euclidean spaces. In particular, our deterministic streaming algorithms store 𝒪(ε^{-2}log(1/(ε))) points. This improves by a factor of ε^{-1} the previous space bound of Agarwal and Sharathkumar (SODA 2010), while retaining the state-of-the-art approximation guarantees, such as √2+ε for Diameter or Farthest Neighbor queries, and also offering a simpler and more complete argument. Moreover, we show that storing Ω(ε^{-1}) points is necessary for a streaming (√2+ε)-approximation of Farthest Pair and Farthest Neighbor queries.
Cite as

Magnús M. Halldórsson, Nicolaos Matsakis, and Pavel Veselý. Streaming Diameter of High-Dimensional Points. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 58:1-58:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.ESA.2025.58,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Matsakis, Nicolaos and Vesel\'{y}, Pavel},
  title =	{{Streaming Diameter of High-Dimensional Points}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{58:1--58:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.58},
  URN =		{urn:nbn:de:0030-drops-245263},
  doi =		{10.4230/LIPIcs.ESA.2025.58},
  annote =	{Keywords: streaming algorithm, farthest pair, diameter, minimum enclosing ball, coreset}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.35
The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon

Authors: Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The Fréchet distance is a popular similarity measure that is well-understood for polygonal curves in ℝ^d: near-quadratic time algorithms exist, and conditional lower bounds suggest that these results cannot be improved significantly, even in one dimension and when approximating with a factor less than three. We consider the special case where the curves bound a simple polygon and distances are measured via geodesics inside this simple polygon. Here the conditional lower bounds do not apply; Efrat et al. (2002) were able to give a near-linear time 2-approximation algorithm. In this paper, we significantly improve upon their result: we present a (1+ε)-approximation algorithm, for any ε > 0, that runs in 𝒪(1/(ε) (n+m log n) log nm log 1/(ε)) time for a simple polygon bounded by two curves with n and m vertices, respectively. To do so, we show how to compute the reachability of specific groups of points in the free space at once, by interpreting the free space as one between separated one-dimensional curves. We solve this one-dimensional problem in near-linear time, generalizing a result by Bringmann and Künnemann (2015). Finally, we give a linear time exact algorithm if the two curves bound a convex polygon.
Cite as

Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann. The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.ESA.2025.35,
  author =	{van der Horst, Thijs and van Kreveld, Marc and Ophelders, Tim and Speckmann, Bettina},
  title =	{{The Geodesic Fr\'{e}chet Distance Between Two Curves Bounding a Simple Polygon}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.35},
  URN =		{urn:nbn:de:0030-drops-245038},
  doi =		{10.4230/LIPIcs.ESA.2025.35},
  annote =	{Keywords: Fr\'{e}chet distance, approximation, geodesic, simple polygon}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.30
A Research Framework to Develop a Real-Time Synchrony Index to Monitor Team Cohesion and Performance in Long-Duration Space Exploration

Authors: Federico Nemmi, Emma Chabani, Laure Boyer, Charlie Madier, and Daniel Lewkowicz

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
As humanity prepares for long-distance space exploration, optimizing group performance, the ability of a group to achieve its goals efficiently, is critical. Astronaut crews will endure isolation, confinement, and operational stress, making group synchrony - the alignment of behaviors, emotions, and physiological states - a key factor in mission success. Synchrony influences team cohesion, performance, and resilience, necessitating effective crew management strategies. This paper proposes a framework for a real-time, unobtrusive index of group synchrony to support astronauts and mission control. Research indicates that team cohesion fluctuates in isolated environments, with reduced communication and interpersonal conflicts emerging over time. A system tracking synchrony could mitigate these issues, providing proactive support and improving remote management. Additionally, it could serve as a cognitive and physiological feedback tool for astronauts and a decision-making aid for mission control, enhancing well-being and efficiency. Our approach integrates behavioral and physiological synchrony measures to assess team cohesion and performance. We propose a multi-modal synchrony index combining movement coordination, communication patterns, and physiological signals such as heart rate, electrodermal activity, and EEG. This index will be validated across different tasks to ensure applicability across diverse mission scenarios. By developing a robust synchrony index, we address a fundamental challenge in space missions: sustaining team effectiveness under extreme conditions. Beyond space exploration, our findings could benefit high-risk, high-isolation teams in submarine crews, polar expeditions, and remote research groups. Our collaboration with the Centre National d'Etudes Spatiales, the Institut de Médecine et de Physiologie Spatiales, and the Toulouse University Hospital marks the first step, with experimental data collection starting this year. Ultimately, this research fosters more adaptive, responsive, and resilient teams for future space missions.
Cite as

Federico Nemmi, Emma Chabani, Laure Boyer, Charlie Madier, and Daniel Lewkowicz. A Research Framework to Develop a Real-Time Synchrony Index to Monitor Team Cohesion and Performance in Long-Duration Space Exploration. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nemmi_et_al:OASIcs.SpaceCHI.2025.30,
  author =	{Nemmi, Federico and Chabani, Emma and Boyer, Laure and Madier, Charlie and Lewkowicz, Daniel},
  title =	{{A Research Framework to Develop a Real-Time Synchrony Index to Monitor Team Cohesion and Performance in Long-Duration Space Exploration}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{30:1--30:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.30},
  URN =		{urn:nbn:de:0030-drops-240200},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.30},
  annote =	{Keywords: Performance, Synchronie, Crew monitoring, Cohesion}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.1
Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics

Authors: Kinter Ren and Mohammad R. Salavatipour

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

Abstract
In this paper we look at various extensions of the classic Traveling Salesman Problem (TSP) on graphs with bounded doubling dimension and bounded treewidth and present approximation schemes for them. Suppose we are given a weighted graph G = (V,E) with a start node s ∈ V, distances on the edges d:E → ℚ^+ and integer k. In k-stroll problem the goal is to find a path from s of minimum length that visits at least k vertices. In k-path we are given an additional end node t ∈ V and the path is supposed to go from s to t. The dual problem to k-stroll is the rooted orienteering in which instead of k we are given a budget B and the goal is to find a walk of length at most B starting at s that visits as many vertices as possible. In the point-to-point orienteering (P2P orienteering) we are given start and end nodes s,t and the walk is supposed to start at s and end at t. In the deadline TSP (which generalizes P2P orienteering) we are given a deadline D(v) for each v ∈ V and the goal is to find a walk starting at s that visits as many vertices as possible before their deadline (where the visit time of a node is the distance travelled from s to that node). The best approximation for rooted orienteering (or P2P orienteering) is (2+ε)-approximation [Chekuri et al., 2012] and O(log n)-approximation for deadline TSP [Nikhil Bansal et al., 2004]. For Euclidean metrics of fixed dimension, Chen and Har-Peled present [Chen and Har-Peled, 2008] a PTAS for rooted orienteering. There is no known approximation scheme for deadline TSP for any metric (not even trees). Our main result is the first approximation scheme for deadline TSP on metrics with bounded doubling dimension (which includes Euclidean metrics). To do so we first we present a quasi-polynomial time approximation scheme for k-path and P2P orienteering on such metrics. More specifically, if G is a metric with doubling dimension κ and aspect ratio Δ, we present a (1+ε)-approximation that runs in time n^{O((logΔ/ε) ^{2κ+1})}. Building upon these, we obtain an approximation scheme for deadline TSP when the distances and deadlines are integer which runs in time n^{O((log Δ/ε) ^{2κ+2})}. The same approach also implies a bicriteria (1+ε,1+ε)-approximation for deadline TSP for when distances and deadlines are in ℚ^+. For graphs with bounded treewidth ω we show how to solve k-path and P2P orienteering exactly in polynomial time and a (1+ε)-approximation for deadline TSP in time n^O((ωlogΔ/ε)²).
Cite as

Kinter Ren and Mohammad R. Salavatipour. Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ren_et_al:LIPIcs.APPROX/RANDOM.2025.1,
  author =	{Ren, Kinter and Salavatipour, Mohammad R.},
  title =	{{Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{1:1--1:22},
  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.1},
  URN =		{urn:nbn:de:0030-drops-243678},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.1},
  annote =	{Keywords: Deadline Traveling Salesman Problem, Orienteering, Doubling Metrics, Approximation algorithm}
}
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}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.8
Multipass Linear Sketches for Geometric LP-Type Problems

Authors: N. Efe Çekirge, William Gay, and David P. Woodruff

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

Abstract
LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinatorial optimization problems, with many important applications in machine learning applications such as classification, bioinformatics, and noisy learning. We study LP-type problems in several streaming and distributed big data models, giving ε-approximation linear sketching algorithms with a focus on the high accuracy regime with low dimensionality d, that is, when d < (1/ε)^0.999. Our main result is an O(ds) pass algorithm with O(s(√d/ε)^{3d/s}) ⋅ poly(d, log (1/ε)) space complexity in words, for any parameter s ∈ [1, d log (1/ε)], to solve ε-approximate LP-type problems of O(d) combinatorial and VC dimension. Notably, by taking s = d log (1/ε), we achieve space complexity polynomial in d and polylogarithmic in 1/ε, presenting exponential improvements in 1/ε over current algorithms. We complement our results by showing lower bounds of (1/ε)^Ω(d) for any 1-pass algorithm solving the (1 + ε)-approximation MEB and linear SVM problems, further motivating our multi-pass approach.
Cite as

N. Efe Çekirge, William Gay, and David P. Woodruff. Multipass Linear Sketches for Geometric LP-Type Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 8:1-8:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cekirge_et_al:LIPIcs.APPROX/RANDOM.2025.8,
  author =	{\c{C}ekirge, N. Efe and Gay, William and Woodruff, David P.},
  title =	{{Multipass Linear Sketches for Geometric LP-Type Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{8:1--8:25},
  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.8},
  URN =		{urn:nbn:de:0030-drops-243741},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.8},
  annote =	{Keywords: Streaming, sketching, LP-type problems}
}
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}
}
  • Refine by Type
  • 56 Document/PDF
  • 42 Document/HTML
  • 3 Artifact

  • Refine by Publication Year
  • 3 2026
  • 41 2025
  • 2 2024
  • 2 2023
  • 4 2020
  • Show More...

  • Refine by Author
  • 18 Mitchell, Joseph S. B.
  • 9 Polishchuk, Valentin
  • 5 Arkin, Esther M.
  • 4 Fekete, Sándor P.
  • 4 Goswami, Mayank
  • Show More...

  • Refine by Series/Journal
  • 51 LIPIcs
  • 2 OASIcs
  • 3 TGDK

  • Refine by Classification
  • 23 Theory of computation → Computational geometry
  • 7 Theory of computation → Design and analysis of algorithms
  • 5 Theory of computation → Approximation algorithms analysis
  • 4 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Theory of computation → Packing and covering problems
  • Show More...

  • Refine by Keyword
  • 4 approximation
  • 3 Fréchet distance
  • 2 Approximation Algorithms
  • 2 Approximation algorithms
  • 2 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