We consider approximation algorithms for the problem of computing an inscribed rectangle
having largest area in a convex polygon on n vertices. If the order of the vertices of the …

We describe a data structure for submatrix maximum queries in Monge matrices or Monge
partial matrices, where a query specifies a contiguous submatrix of the given matrix, and its …

We describe a data structure for submatrix maximum queries in Monge matrices or partial
Monge matrices, where a query seeks the maximum element in a contiguous submatrix of …

We solve an interesting optimization problem motivated by tolerancing metrology, paper
position sensing, and facility location: What rectangle fits best a given set of points? This …

Classical separability problem involving multi-color point sets is an important area of study in
computational geometry. In this paper, we study different separability problems for …

This paper considers the problem of finding maximum volume (axis-aligned) inscribed
boxes in a compact convex set, defined by a finite number of convex inequalities, and …

Planar Case of the Maximum Box and Related Problems Page 1 CCCG 2003, Halifax, Nova
Scotia, August 11–13, 2003 Planar Case of the Maximum Box and Related Problems ∗ Ying …

Given a set R of n red points and a set B of m blue points, we study the problem of finding a
rectangle that contains all the red points, the minimum number of blue points and has the …

This paper studies empty squares in arbitrary orientation among a set P of n points in the
plane. We prove that the number of empty squares with four contact pairs is between Ω (n) …

In this paper, we address the minimum-area rectangular and square annulus problem,
which asks a rectangular or square annulus of minimum area, either in a fixed orientation or …