19 citations · 66 across the 26 of their papers we have counts for
6 papers · 1 filter
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…
Critical Placements of a Square or Circle amidst Trajectories for Junction Detection
Ingo van Duijn, Irina Kostitsyna, Marc van Kreveld +1
Motivated by automated junction recognition in tracking data, we study a problem of placing a square or disc of fixed size in an arrangement of lines or line segments in the plane.…
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…
Mapping polygons to the grid with small Hausdorff and Fréchet distance
Quirijn W. Bouts, Irina Kostitsyna, Marc van Kreveld +3
We show how to represent a simple polygon by a grid (pixel-based) polygon that is simple and whose Hausdorff or Fréchet distance to is small. For any simple polygon …
Computing Nonsimple Polygons of Minimum Perimeter
Sándor P. Fekete, Andreas Haas, Michael Hemmer +8
We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertic…
On the complexity of minimum-link path problems
Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk +1
We revisit the minimum-link path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings…