4 papers · 1 filter
Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time
Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth +1
A fundamental question is whether one can maintain a maximum independent set in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. Alread…
Reconfiguration of Polygonal Subdivisions via Recombination
Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine +2
Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon $\mathcal{R…
Observation Routes and External Watchman Routes
Adrian Dumitrescu, Csaba D. Tóth
We introduce the Observation Route Problem () defined as follows: Given a set of pairwise disjoint compact regions in the plane, find a shortest tour (route) such…
Maximal Distortion of Geodesic Diameters in Polygonal Domains
Adrian Dumitrescu, Csaba D. Tóth
For a polygon with holes in the plane, we denote by the ratio between the geodesic and the Euclidean diameters of . It is shown that over all convex polygons wi…