3 papers
cs.CG2019
On Romeo and Juliet Problems: Minimizing Distance-to-Sight
Hee-Kap Ahn, Eunjin Oh, Lena Schlipf +2
We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points and in a simple polygon w…
cs.CG2017
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…
cs.CG2016
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…