Approximations with Axis-Aligned Rectangles (Extended Abstract)

It is shown that for any $n$ disjoint axis-aligned fat rectangles in three-space there is a binary space partition (BSP) of $O(n\log^8 n)$ size and $O(\log^5 n)$ height and it can be constructed in $O(n \,\mathrm{polylog}\, n)$ time. This improves ...

The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean distance. We consider a generalized version of this notion, ...

Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P. We present an ...