19 citations · 22 across the 10 of their papers we have counts for
25 papers
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Bahareh Banyassady, Mark de Berg, Karl Bringmann +6
We consider the unlabeled motion-planning problem of unit-disc robots moving in a simple polygonal workspace of edges. The goal is to find a motion plan that moves the robo…
The Shortest Path with Increasing Chords in a Simple Polygon
Mart Hagedoorn, Irina Kostitsyna
We study the problem of finding the shortest path with increasing chords in a simple polygon. A path has increasing chords if and only if for any points a, b, c, and d that lie on…
Embedding Ray Intersection Graphs and Global Curve Simplification
Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler
We prove that circle graphs (intersection graphs of circle chords) can be embedded as intersection graphs of rays in the plane with polynomial-size bit complexity. We use this embe…
Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility
David Kirkpatrick, Irina Kostitsyna, Alfredo Navarra +2
Among fundamental problems in the context of distributed computing by autonomous mobile entities, one of the most representative and well studied is {\sc Point Convergence}: given…
Dots & Boxes is PSPACE-complete
Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna +1
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a cha…
Minimum Scan Cover and Variants -- Theory and Experiments
Kevin Buchin, Sándor P. Fekete, Alexander Hill +5
We consider a spectrum of geometric optimization problems motivated by contexts such as satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Cos…