19 citations · 66 across the 26 of their papers we have counts for
31 papers · 1 filter
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.…
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…
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…
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…
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…
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…
Global Curve Simplification
Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler +2
Due to its many applications, \emph{curve simplification} is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information s…
Approximating -center clustering for curves
Kevin Buchin, Anne Driemel, Joachim Gudmundsson +4
The Euclidean -center problem is a classical problem that has been extensively studied in computer science. Given a set of points in Euclidean space, the probl…
An Optimal Algorithm to Compute the Inverse Beacon Attraction Region
Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman +1
The beacon model is a recent paradigm for guiding the trajectory of messages or small robotic agents in complex environments. A beacon is a fixed point with an attraction pull that…
Folding Polyominoes into (Poly)Cubes
Oswin Aichholzer, Michael Biro, Erik D. Demaine +6
We study the problem of folding a polyomino into a polycube , allowing faces of to be covered multiple times. First, we define a variety of folding models according to w…
The Painter's Problem: covering a grid with colored connected polygons
Arthur van Goethem, Irina Kostitsyna, Marc van Kreveld +3
Motivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors . Each cell in the grid is assigned a subs…
Self-approaching paths in simple polygons
Prosenjit Bose, Irina Kostitsyna, Stefan Langerman
We study self-approaching paths that are contained in a simple polygon. A self-approaching path is a directed curve connecting two points such that the Euclidean distance between a…
Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
Nicolas Bonichon, Prosenjit Bose, Paz Carmi +3
A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is - and -monotone. Angle-monotone graphs are -spa…