BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Irina Kostitsyna contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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 the path in that order, |ad| >= |bc|. In this paper we show that the shortest path with increasing chords is unique and present an algorithm to construct it.
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 asynchronously. Turning Machines are a simple 1D to 2D folding model, also easily generalisable to 2D to 3D folding. A Turning Machine starts out as a line of connected monomers in the discrete plane, each with an associated turning number. A monomer turns relative to its neighbours, executing a unit-distance translation that drags other monomers along with it, and through collective motion the initial set of monomers eventually folds into a programmed shape. We provide a suite of tools for reasoning about Turning Machines by fully characterising their ability to execute line rotations: executing an almost-full line rotation of $5π/3$ radians is possible, yet a full $2π$ rotation is impossible. Furthermore, line rotations up to $5π/3$ are executed efficiently, in $O(\log n)$ expected time in our continuous time Markov chain time model. We then show that such line-rotations represent a fundamental primitive in the model, by using them to efficiently and asynchronously fold shapes. In particular, arbitrarily large zig-zag-rastered squares and zig-zag paths are foldable, as are $y$-monotone shapes albeit with error (bounded by perimeter length). Finally, we give shapes that despite having paths that traverse all their points, are in fact impossible to fold, as well as techniques for folding certain classes of (scaled) shapes without error. Our approach relies on careful geometric-based analyses of the feats possible and impossible by a very simple robotic system, and pushes conceptional hardness towards mathematical analysis and away from molecular implementation.
We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time $O(n \log n + mn + m^2)$ if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance $4$ apart, any two target positions are at least distance $4$ apart, and any pair of a start and a target positions is at least distance $3$ apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.
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 phases: a preprocessing phase, in which we have access only to R, followed by a reconstruction phase, in which we have access to points in P at a certain retrieval cost C per point. We study the following algorithmic question: how fast can we construct the pareto front of P in the preprocessing model? We show that if R is a set of pairwise-disjoint axis-aligned rectangles, then we can preprocess R to reconstruct the Pareto front of P efficiently. To refine our algorithmic analysis, we introduce a new notion of algorithmic optimality which relates to the entropy of the uncertainty regions. Our proposed uncertainty-region optimality falls on the spectrum between worst-case optimality and instance optimality. We prove that instance optimality is unobtainable in the preprocessing model, whenever the classic algorithmic problem reduces to sorting. Our results are worst-case optimal in the preprocessing phase; in the reconstruction phase, our results are uncertainty-region optimal with respect to real RAM instructions, and instance optimal with respect to point retrievals.
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 use of discrete modular structures for in-space assembly and relatively small scale robotics that are able to modify and traverse the structure. This paper addresses the algorithmic problems in scaling reconfigurable space structures built through robotic construction, where reconfiguration is defined as the problem of transforming an initial structure into a different goal configuration. We analyze different algorithmic paradigms and present corresponding abstractions and graph formulations, examining specialized algorithms that consider discretized space and time steps. We then discuss fundamental design trades for different computational architectures, such as centralized versus distributed, and present two representative algorithms as concrete examples for comparison. We analyze how those algorithms achieve different objective functions and goals, such as minimization of total distance traveled, maximization of fault-tolerance, or minimization of total time spent in assembly. This is meant to offer an impression of algorithmic constraints on scalability of corresponding structural and robotic design. From this study, a set of recommendations is developed on where and when to use each paradigm, as well as implications for physical robotic and structural system design.
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 area. We show that deciding whether the game can be won from a given state, is NP-hard. We do so by a reduction from vertex-disjoint cycle packing in cubic planar graphs, including a self-contained reduction from planar 3-Satisfiability to this cycle-packing problem. This also provides a simple proof of the NP-hardness of the related game Dots & Boxes. For points in convex position, we discuss a greedy strategy for Dots & Polygons.
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 sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special \emph{simple} holes guarantee foldability.
Due to its many applications, \emph{curve simplification} is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve $P$ with $n$ vertices, the goal is to find another polygonal curve $P'$ with a smaller number of vertices such that $P'$ is sufficiently similar to $P$. Quality guarantees of a simplification are usually given in a \emph{local} sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work, we aim to provide a systematic overview of curve simplification problems under \emph{global} distance measures that bound the distance between $P$ and $P'$. We consider six different curve distance measures: three variants of the \emph{Hausdorff} distance and three variants of the \emph{Fréchet} distance. And we study different restrictions on the choice of vertices for $P'$. We provide polynomial-time algorithms for some variants of the global curve simplification problem and show NP-hardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area.
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 positions. We consider the specific case of unlabeled disc robots of two different sizes. That is, within one class of robots, where a class is given by the robots' size, any robot can be moved to any of the corresponding target positions. We prove that the decision problem of whether there exists a schedule moving the robots to the target positions is PSPACE-hard.