  $ \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}}
\newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Mh}[1]{#1}
\newcommand{\query}{q} \newcommand{\eps}{\varepsilon}
\newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}}
\newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\|
{#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$ A set $P$ of
$n$ points in the plane, induces a set of Delaunay-type axis-parallel
rectangles $\mathcal{R}$, potentially of quadratic size, where an axis-parallel
rectangle is in $\mathcal{R}$, if it has two points of $P$ as corners, and no
other point of $P$ in it. We study various algorithmic problems related to this
set of rectangles, including how to compute it, in near linear time, and handle
various algorithmic tasks on it, such as computing its union and depth. The set
of rectangles $\mathcal{R}$ induces the rectangle influence graph $G =
(P,\mathcal{R})$, which we also study. Potentially our most interesting result
is showing that this graph can be described as the union of $O(n)$ bicliques,
where the total weight of the bicliques is $O(n \log^2 n)$. Here, the weight of
a bicliques is the cardinality of its vertices.
