In computational geometry the following problem often arises: given a set of points, determine the smallest geometric shape of a certain type that contains them. A natural variation introduces a parameter $k$, asking for a shape that contains k points rather than all of them. This leads to the smallest $k$-point enclosing rectangle problem. In this thesis, we present a simple divide-and-conquer approach which is currently the state of the art. We also study several extensions of the problem and show how the method adapts while retaining its efficiency.
|
