27 citations · 104 across the 19 of their papers we have counts for
16 papers · 1 filter
Placing your Coins on a Shelf
Helmut Alt, Kevin Buchin, Steven Chaplick +4
We consider the problem of packing a family of disks "on a shelf", that is, such that each disk touches the -axis from above and such that no two disks overlap. We prove that th…
Covering many points with a small-area box
Mark de Berg, Sergio Cabello, Otfried Cheong +2
Let be a set of points in the plane. We show how to find, for a given integer , the smallest-area axis-parallel rectangle that covers points of in $O(nk^2 \log…
Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees
Ulrike Große, Joachim Gudmundsson, Christian Knauer +2
We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We pr…
Fréchet Distance for Curves, Revisited
Boris Aronov, Sariel Har-Peled, Christian Knauer +2
$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\eps}{\varepsilon} \newcommand{\SetX}{\mathsf{X}} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\m…
Finding Largest Rectangles in Convex Polygons
Sergio Cabello, Otfried Cheong, Christian Knauer +1
We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with vertices. We…
Finding a largest empty convex subset in space is W[1]-hard
Panos Giannopoulos, Christian Knauer
We consider the following problem: Given a point set in space find a largest subset that is in convex position and whose convex hull is empty. We show that the (decision version of…