182 citations · 549 across the 43 of their papers we have counts for
22 papers · 1 filter
The Two-Squirrel Problem and Its Relatives
Sergey Bereg, Yuya Higashikawa, Naoki Katoh +3
In this paper, we start with a variation of the star cover problem called the Two-Squirrel problem. Given a set of points in the plane, and two sites and , comp…
Removing Popular Faces in Curve Arrangements
Phoebe de Nooijer, Soeren Terziadis, Alexandra Weinberger +4
A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate…
The Largest Contained Quadrilateral and the Smallest Enclosing Parallelogram of a Convex Polygon
Günter Rote
We present a linear-time algorithm for finding the quadrilateral of largest area contained in a convex polygon, and we show that it is closely related to an old algorithm for the s…
Geometric Multicut
Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler +1
We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" , i.e., a union of curves of minimum total length, that…
Approximate Minimum-Weight Matching with Outliers under Translation
Pankaj K. Agarwal, Haim Kaplan, Geva Kipper +4
Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a tran…
Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity
Boris Klemz, Günter Rote
We introduce and study the problem Ordered Level Planarity which asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such th…