Csaba D. Tóth

collaborators

Showing cs.CGShow all

7 papers · 1 filter

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

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.CG2026

Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Sujoy Bhore, SÃ¡ndor Kisfaludi-Bak, Lazar MilenkoviÄ +3

A Euclidean noncrossing Steiner $(1 + I^µ)$ -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

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…