Csaba D. Tóth

activity

20242026

collaborators

9 papers

cs.CG2026

Online Geometric Packing through Online TSP Scheduling

Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae +3

We consider the problem of online packing of convex polygons into a strip by translations. While online algorithms with a constant competitive ratio have been known for rectangles…

cs.CG2026

Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Sujoy Bhore, Sándor Kisfaludi-Bak, Lazar Milenković +3

A Euclidean noncrossing Steiner $(1 + ε)$ -spanner for a point set $P \subset R^{2}$ is a planar straight-line graph that, for any two points $a, b \in P$ , contains a path whose…

cs.CG2025

Approximating Euclidean Shallow-Light Trees

Hung Le, Shay Solomon, Cuong Than +2

For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$ , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum…

cs.CG2025

Online Hitting Set for Axis-Aligned Squares

Minati De, Satyam Singh, Csaba D. Tóth

We are given a set $P$ of $n$ points in the plane, and a sequence of axis-aligned squares that arrive in an online fashion. The online hitting set problem consists of maintaining,…

cs.CG2025

The Price of Connectivity Augmentation on Planar Graphs

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine +5

Given two classes of graphs, $G_{1} \subseteq G_{2}$ , and a $c$ -connected graph $G \in G_{1}$ , we wish to augment $G$ with a smallest cardinality set of new e…

cs.DS2025

Approximate Light Spanners in Planar Graphs

Hung Le, Shay Solomon, Cuong Than +2

In their seminal paper, Althöfer et al. (DCG 1993) introduced the {\em greedy spanner} and showed that, for any weighted planar graph $G$ , the weight of the greedy $(1 + ε)$ -spanner…

math.CO2025

Erdős-Szekeres Maker-Breaker Games

Aleksa Džuklevski, Dömötör Pálvölgyi, Alexey Pokrovskiy +3

We present new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be…

cs.CG2025

Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6

Let $S$ be a set of $n$ points in $R^{d}$ , where $d \geq 2$ is a constant, and let $H_{1}, H_{2}, \dots, H_{m + 1}$ be a sequence of vertical hyperplanes that are sorted by their fi…

cs.CG2024

Online Hitting Sets for Disks of Bounded Radii

Minati De, Satyam Singh, Csaba D. Tóth

We present algorithms for the online minimum hitting set problem in geometric range spaces: given a set $P$ of $n$ points in the plane and a sequence of geometric objects that arri…