19 citations · 66 across the 26 of their papers we have counts for
7 papers · 1 filter
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…
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares
Hugo A. Akitaya, Erik D. Demaine, Matias Korman +6
A well-established theoretical model for modular robots in two dimensions are edge-connected configurations of square modules, which can reconfigure through so-called sliding moves…
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…
Chasing Puppies: Mobile Beacon Routing on Closed Curves
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna +5
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve…
Preprocessing Imprecise Points for the Pareto Front
Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler +1
In the preprocessing model for uncertain data we are given a set of regions R which model the uncertainty associated with an unknown set of points P. In this model there are two ph…