9 papers
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…
Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers
Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6
Let be a set of points in , where is a constant, and let be a sequence of vertical hyperplanes that are sorted by their fi…
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…
Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
Sujoy Bhore, Sándor Kisfaludi-Bak, Lazar MilenkoviÄ +3
A Euclidean noncrossing Steiner -spanner for a point set is a planar straight-line graph that, for any two points , contains a path whose…
Approximating Euclidean Shallow-Light Trees
Hung Le, Shay Solomon, Cuong Than +2
For a weighted graph and a designated source vertex , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source and a minimum…
Online Hitting Set for Axis-Aligned Squares
Minati De, Satyam Singh, Csaba D. Tóth
We are given a set of 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,…