19 citations · 66 across the 26 of their papers we have counts for
41 papers
Theoretical analysis of beaconless geocast protocols in 1D
Joachim Gudmundsson, Irina Kostitsyna, Maarten Löffler +3
Beaconless geocast protocols are routing protocols used to send messages in mobile ad-hoc wireless networks, in which the only information available to each node is its own locatio…
Optimal In-Place Compaction of Sliding Cubes
Irina Kostitsyna, Tim Ophelders, Irene Parada +3
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes.…
Universal Coating by 3D Hybrid Programmable Matter
Irina Kostitsyna, David Liedtke, Christian Scheideler
Motivated by the prospect of nano-robots that assist human physiological functions at the nanoscale, we investigate the coating problem in the three-dimensional model for hybrid pr…
Morphing Planar Graph Drawings Through 3D
Kevin Buchin, Will Evans, Fabrizio Frati +4
In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-li…
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…
On the Computational Power of Energy-Constrained Mobile Robots: Algorithms and Cross-Model Analysis
Kevin Buchin, Paola Flocchini, Irina Kostitsyna +3
We consider distributed systems of identical autonomous computational entities, called robots, moving and operating in the plane in synchronous Look-Compute-Move (LCM) cycles. The…
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…
Fast Reconfiguration for Programmable Matter
Irina Kostitsyna, Tom Peters, Bettina Speckmann
The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material. Even though the particles are restricted to local comm…
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…
Turning Machines: a simple algorithmic model for molecular robotics
Irina Kostitsyna, Cai Wood, Damien Woods
Molecular robotics is challenging, so it seems best to keep it simple. We consider an abstract molecular robotics model based on simple folding instructions that execute asynchrono…
Algorithmic Approaches to Reconfigurable Assembly Systems
Allan Costa, Benjamin Jenett, Irina Kostitsyna +3
Assembly of large scale structural systems in space is understood as critical to serving applications that cannot be deployed from a single launch. Recent literature proposes the u…
Dots & Polygons
Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna +3
We present a new game, Dots & Polygons, played on a planar point set. Players take turns connecting two points, and when a player closes a (simple) polygon, the player scores its a…
Multi-robot motion planning of k-colored discs is PSPACE-hard
Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna +2
In the problem of multi-robot motion planning, a group of robots, placed in a polygonal domain with obstacles, must be moved from their starting positions to a set of target positi…
Folding Polyominoes with Holes into a Cube
Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung +9
When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present s…
Most vital segment barriers
Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk +1
We study continuous analogues of "vitality" for discrete network flows/paths, and consider problems related to placing segment barriers that have highest impact on a flow/path in a…
Preprocessing Ambiguous Imprecise Points
Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler +1
Let be a set of regions and let be an (unknown) point set with . Region represents the uncertainty r…
Fragile Complexity of Comparison-Based Algorithms
Peyman Afshani, Rolf Fagerberg, David Hammer +5
We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the ma…
Convex partial transversals of planar regions
Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld +6
We consider the problem of testing, for a given set of planar regions and an integer , whether there exists a convex shape whose boundary intersects at least region…