Computational Geometry: Theory and Applications

A geometric graph is a graph whose vertex set is a set of points in general position in the plane, and its edges are straight line segments joining these points. We show that for every integer k ≥ 2, there exists a constant c > 0 such that the ...

We consider an optimization problem of inscribing a unit rectangle in a convex polygon. An axis-aligned unit rectangle is an axis-aligned rectangle whose horizontal sides are of length 1. A unit rectangle of orientation θ is a copy of an axis-...

We study the uniform 2-dimensional vector multiple knapsack (2VMK) problem, a natural variant of multiple knapsack arising in real-world applications such as virtual machine placement. The input for 2VMK is a set of items, each associated with a ...

A packing of disks in the plane is a set of disks with disjoint interiors. This paper is a survey of some open questions about such packings. It is organized into five themes: compacity, conjugacy, density, uniformity and computability.