# An Instance-optimal Algorithm for Bichromatic Rectangular Visibility

Jean Cardinal Department of Computer Science, Université libre de Bruxelles,
<EMAIL_ADDRESS>Justin Dallant Department of Computer Science, Université
libre de Bruxelles<EMAIL_ADDRESS>Supported by the French Community of
Belgium via the funding of a FRIA grant. John Iacono Department of Computer
Science, Université libre de Bruxelles<EMAIL_ADDRESS>Supported by the
Fonds de la Recherche Scientifique-FNRS under Grant no MISU F 6001 1.

###### Abstract

Afshani, Barbay and Chan (2017) introduced the notion of instance-optimal
algorithm in the order-oblivious setting. An algorithm $A$ is instance-optimal
in the order-oblivious setting for a certain class of algorithms $\mathcal{A}$
if the following hold:

  * •

$A$ takes as input a sequence of objects from some domain;

  * •

for any instance $\sigma$ and any algorithm $A^{\prime}\in\mathcal{A}$, the
runtime of $A$ on $\sigma$ is at most a constant factor removed from the
runtime of $A^{\prime}$ on the worst possible permutation of $\sigma$.

If we identify permutations of a sequence as representing the same instance,
this essentially states that $A$ is optimal on every possible input (and not
only in the worst case).

We design instance-optimal algorithms for the problem of reporting, given a
bichromatic set of points in the plane $S$, all pairs consisting of points of
different color which span an empty axis-aligned rectangle (or reporting all
points which appear in such a pair). This problem has applications for
training-set reduction in nearest-neighbour classifiers. It is also related to
the problem consisting of finding the decision boundaries of a euclidean
nearest-neighbour classifier, for which Bremner et al. (2005) gave an optimal
output-sensitive algorithm.

By showing the existence of an instance-optimal algorithm in the order-
oblivious setting for this problem we push the methods of Afshani et al.
closer to their limits by adapting and extending them to a setting which
exhibits highly non-local features. Previous problems for which instance-
optimal algorithms were proven to exist were based solely on local
relationships between points in a set.

##  1 Introduction

In the theoretical study of algorithms one often quantifies the performance of
an algorithm in terms of the worst case or average running time over a
distribution of inputs of a given size. Sometimes, more precise statements can
be made about the speed of an algorithm on certain instances by expressing the
running time in terms of some parameter depending on the input. One class of
such algorithms are the so-called output-sensitive algorithms, where the
parameter is the size of the output. In computational geometry, a classical
example is computing the convex hull of a set of $n$ points in the plane in
$\mathcal{O}(n\log h)$ time, where $h$ is the size of the convex hull [16, 7].
More recently, Afshani et. al. [1] introduced a specific notion of _instance
optimality in the order-oblivious setting_ and designed algorithms with this
property for different problems on point sets. Roughly speaking, an algorithm
is instance optimal in a certain class of algorithms $\mathcal{A}$ if on any
input sequence $S$, its performance on $S$ is at most a constant factor
removed from the best performance of any algorithm in $\mathcal{A}$ on $S$. In
the order-oblivious setting, performance is defined as the worst-case runtime
over all permutations of the input sequence (the motivation behind this will
be made clear below). A common characteristic of most problems solved in [1]
is that they are based around local relations between points in $S$, in the
sense that the relation between two points $p,q\in S$ depends solely on their
coordinates and not on those of any other point in $S$. This is important
because it allows one to decompose certain queries into independent queries on
a partition of $S$. In this paper we push these methods closer to their limits
by adapting and applying them to a problem which does not fit in this
framework.

The studied problem Here we consider the following problem: given a set $S$ of
points $n$ in the plane with distinct $x$ and $y$ coordinates, each colored
red or blue, report the red/blue pairs of points such that the rectangles they
span contain no point of $S$ in their interior. This again has applications to
machine learning and more specifically nearest-neighbour classifiers. Indeed,
by solving this problem and discarding all points which do not not appear in
such a pair, we obtain a (possibly much smaller) set of points where for any
point $y$ in the plane, the color of its nearest neighbour is the same as in
the original set of points for the $L_{1}$ distance (as pointed out in [12],
where this problem was perhaps first studied). This remains true even when a
priori unknown (and possibly non-linear) scalings might be applied to the $x$
and $y$ axis after this preprocessing step. In fact, the resulting set of
points consists of exactly those necessary for this to hold, so this
constitutes an optimal reduction of the training set in that sense. Note that
this problem does not fit in the general framework of [1], as whether two
point span an empty rectangle depends on the position of all other points.

Related works Pairs of points spanning empty rectangles and the corresponding
graphs have been studied at numerous occasions in the past, under various
names. They are called _rectangular influence graphs_ in [12], which discusses
applications to data clustering and classification. In [11] a similar relation
is called _direct dominance_ , and a worst-case optimal algorithm to report
all pairs of related points is given. This algorithm runs in $O(n\log n+h)$
time, where $h$ is the size of the output. A straightforward adaptation yields
an algorithm with the same running time for the bichromatic problem studied
here. In [19] this relation is called _rectangular visibility_ and a different
algorithm with the same running time is given as well as algorithms for the
dynamic query setting. The expected size of a largest independent set in this
graph is studied in [9] (where they call such graphs _Delaunay graphs with
respect to rectangles_). Generalizations and variations of this type of
relation between points have also been widely studied [18, 17, 6, 2, 13, 15,
14, 20, 10]. Another problem of note which is closely related to the one we
study here is the following: given a set $S$ of $n$ points in the plane, each
colored red or blue, compute the subset of edges of the Voronoï diagram of $S$
which are adjacent to both a site corresponding to a blue point and a site
corresponding to a red point. This problem has some relevance to machine
learning as we can equivalently state it as finding the boundaries of a
nearest-neighbour classifier with two classes in the plane. A third
formulation is finding the pairs of red and blue points such that there is an
empty disk whose boundary passes through both. In [5], Bremner et. al. show
that this problem can be solved in output-sensitive optimal $\mathcal{O}(n\log
h)$ time, where $h$ is the size of the output. It is an interesting open
problem to find instance-optimal algorithms for this problem in the order-
oblivious setting (or prove that no such algorithm exists).

Paper organization In Section 2 we motivate and state more precisely the
notion of instance-optimality we work with in this paper. In Section 3 we
define the problem formally and give an instance lower bound in the order-
oblivious model by adapting the adversarial argument of [1]. The key new
ingredients are a new definition of safety and a way to deal with the fact
that here the adversary cannot necessarily change the expected output of the
algorithm by moving a single point inside a so-called non-safe region. In
Section 4 we give an algorithm and prove that its runtime matches the lower
bound. The main observation which makes this work is that while the algorithms
in [1] require the safety queries to be decomposable (which they are not
here), we can afford to do some preprocessing to make them behave as if they
were decomposable, as long as the amount of work done stays within a constant
of the lower bound. In section 5 we mention that when competing against
algorithms which can do linear queries, instance-optimality in the order-
oblivious setting is impossible.

##  2 Instance optimality in the order-oblivious setting and model of
computation

Ideally, we would like to consider a very strong notion of optimality, where
an algorithm is optimal if on every instance its runtime is at most a constant
factor removed from the algorithm with the smallest runtime on that particular
instance. There is an obvious flaw with this definition, as for every instance
we can have an algorithm “specialized” for that instance, which simply checks
if the input is the one it is specialized for then returns the expected output
without any further computation when it is the case (and spends however much
time it needs to compute the correct output otherwise). For problems which are
not solvable in linear time in the worst-case, this prohibits the existence of
such optimal algorithms. One way to get around this issue in some cases and
get a meaningful notion of instance-optimality is the following, taken from
[1].

######  Definition 1.

Consider a problem where the input consists of a sequence of $n$ elements from
a domain ${\cal D}$. Consider a class $\mathcal{A}$ of algorithms. A _correct_
algorithm refers to an algorithm that outputs a correct answer for every
possible sequence of elements in ${\cal D}$. For a set $S$ of $n$ elements in
${\cal D}$, let $T_{A}(S)$ denote the maximum running time of $A$ on input
$\sigma$ over all $n!$ possible permutations $\sigma$ of $S$. Let $\mbox{\rm
OPT}(S)$ denote the minimum of $T_{A^{\prime}}(S)$ over all correct algorithms
$A^{\prime}\in\mathcal{A}$. If $A\in\mathcal{A}$ is a correct algorithm such
that $T_{A}(S)\leq O(1)\cdot\mbox{\rm OPT}(S)$ for every set $S$, then we say
$A$ is _instance-optimal in the order-oblivious setting_.

By measuring the performance of an algorithm on an instance as the maximum
runtime over all permutations of the instance elements, the algorithm can no
longer take advantage of the order in which the input elements are presented.
In particular, simply checking if the input is a specific sequence is no
longer a good strategy. Here, the domain $\mathcal{D}$ consists of all points
in the plane, colored red or blue. An instance is a sequence of points, no two
sharing the same $x$ or $y$ coordinate. However, we really want to consider
this sequence as a set of points, as the order in which the points are
presented does not change the instance conceptually. Thus, it makes sense for
us to consider a performance metric for which algorithms cannot take advantage
of this order. For the class of algorithms $\mathcal{A}$, we will consider
algorithms in a restricted real RAM model where the input can only be accessed
through comparison queries. That is, the algorithms can compare the $x$ or $y$
coordinates of two points but not, for example, evaluate arbitrary arithmetic
expressions on these coordinates. We refer to such algorithms as _comparison-
based algorithms_. The lower bound works even for a stronger model of
computation, comparison-based decision trees (assuming at least a unit cost
for every point returned in the output). We could also allow the comparison of
the $x$ coordinate of a point with the $y$ coordinate of another without
changing any of the results of this paper.

##  3 Lower-bound for comparison-based algorithms in the order-oblivious
setting

#### Some basic notations and definitions

Throughout this section we consider a set $S$ of $n$ red and blue points in
the plane. We assume that $S$ is non-degenerate, in the sense that no two
points in $S$ share the same $x$ or $y$ coordinate (in particular, all points
are distinct). If $p$ is a point, we will denote its $x$ and $y$ coordinates
as $x(p)$ and $y(p)$ respectively and its color as $c(p)$.

######  Definition 2.

A point $p$ _dominates_ $q\neq p$ if $x(p)\geq x(q)$ and $y(p)\geq y(q)$. A
point is _maximal_ (resp.  _minimal_) in $S$ if is dominated by (resp.
dominates) no point in $S$.

######  Definition 3 (Visible and participating points).

Let $p,q$ be two points in $S$. We say that $q$ is _visible_ from $p$ in $S$
(or that $p$ _sees_ $q$ in $S$) if the axis-aligned box spanned by $p$ and $q$
contains no point of $S$ in its interior. We say that $p\in S$ _participates_
in $S$ if it is visible from a point in $S$ of the opposite color. We will
omit the set $S$ when it is clear from context.

The problems we want to solve can thus be restated as follows.

######  Problem 4 (Reporting participating points).

Report all points which participate in $S$.

######  Problem 5 (Reporting red-blue pairs of visible points).

Report all red-blue pairs of points $(p,q)$ such that $p$ and $q$ see each
other in $S$.

The following definitions will also be useful for us.

######  Definition 6.

We call the set of minimal points of $S$ the _NE -minimal-set_ of $S$ (for
“North-East-minimal set”). The _NW -minimal-set_, _SE -minimal-set_ and _SW
-minimal-set_ of $S$ are defined symmetrically (see Figure 2). In particular,
the SE-minimal set of $S$ is the set of maximal points in $S$.

Figure 1: A set of points $S$ and the four minimal-sets of $S$. No point in
the shaded regions can appear on the corresponding minimal-sets.

Figure 2: The four quadrants of an axis-aligned box $B$. The shaded region
corresponds to $cross(B)$.

######  Definition 7.

Let $B$ be an axis-aligned box. We denote the $x$ coordinate of the right
boundary (resp. left boundary) of $B$ as $x_{\max}(B)$ (resp. $x_{\min}(B)$).
We denote the $y$ coordinate of the top boundary (resp. bottom boundary) of
$B$ as $y_{\max}(B)$ (resp. $y_{\min}(B)$).

The _cross_ of $B$, denoted as $cross(B)$ is the set of points $p$ in the
plane such that $x_{\min}(B)\leq x(p)\leq x_{\max}(B)$ or $y_{\min}(B)\leq
y(p)\leq y_{\max}(B)$.

The _quadrants_ of $B$ are the connected components of
$\mathbb{R}^{2}\setminus cross(B)$. We call the four components the _NE
-quadrant_, _NW -quadrant_, _SE -quadrant_ and _SW -quadrant_, denoted as
$\mbox{\rm NE}(B)$, $\mbox{\rm NW}(B)$, $\mbox{\rm SE}(B)$ and $\mbox{\rm
SW}(B)$ respectively (see Figure 2).

All boxes we consider are axis-aligned boxes in the plane. For ease of
exposition, we assume that all boxes we consider have no point of $S$ on the
boundaries of their four quadrants.

#### Lower Bound

Figure 3: A red-safe box $B$.

We prove an entropy-like lower bound on the number of comparisons which have
to be done to solve the problems of reporting participating points in the
order-oblivious setting. The proof and terminology are largely inspired from
the lower bound proofs in [1] but some additional arguments, which we
underline later, are required. We need a few definitions in order to state our
lower bound.

######  Definition 8.

An axis-aligned box $B$ is _red-cross-safe_ (resp.  _blue-cross-safe_) for $S$
if all points in $S\cap cross(B)$ are red (resp. blue). It is _cross-safe_ if
it is red-cross-safe or blue-cross-safe.

It is _red-safe_ if it is red-cross-safe and the NE-minimal (resp. NW-minimal,
SE-minimal, SW-minimal) set of $S\cap\mbox{\rm NE}(B)$ (resp. $S\cap\mbox{\rm
NW}(B)$, $S\cap\mbox{\rm SE}(B)$, $S\cap\mbox{\rm SW}(B)$) is red (see Figure
3). We define _blue-safe_ boxes similarly. A box is _safe_ if it is red-safe
or blue-safe.

A subset $S^{\prime}\in S$ has one of these properties if it can be enclosed
by a box with the property.

Notice that if a subset $S^{\prime}\in S$ is safe, then no point in in
$S^{\prime}$ participates in $S$. Thus, in an intuitive sense, a partition of
non-participating points into safe subsets can be seen as a certificate for
the fact that these points do not participate. The minimal entropy of such a
partition is then the minimal amount of information required to encode such a
certificate.

######  Definition 9.

A partition $\Pi$ of $S$ is _respectful_ if every member $S_{k}\in\Pi$ is a
singleton or a safe subset of $S$. The _entropy_ of a partition $\Pi$ is
${\cal H}(\Pi):=\sum_{S_{k}\in\Pi}\frac{|S_{k}|}{n}\log\frac{n}{|S_{k}|}$. The
_structural entropy_ ${\cal H}(S)$ of $S$ is the minimum of ${\cal H}(\Pi)$
over all respectful partitions $\Pi$ of $S$.

We can now state our lower bound:

######  Theorem 10.

For the problem of reporting participating points in the order-oblivious
comparison-based model, $\mbox{\rm OPT}(S)\in\Omega(n({\cal H}(S)+1))$.
Consequently, for reporting red-blue pairs of visible points, $\mbox{\rm
OPT}(S)\in\Omega(n({\cal H}(S)+1)+h)$, where $h$ is the size of the output.

The proof is similar to what can be found in [1]. In their case however, if a
point can be moved anywhere inside a non-safe box then it can be moved in a
way that changes the expected output of the algorithm. In our case, we can do
something similar but sometimes need to move multiple points to affect the
expected output (but a constant number are enough). We use a simple argument
about the maximum number of chips which can be placed on a tree in a
constrained way to show that this has no impact on the lower bound.

To prove Theorem 10, we will need a few lemmas.

######  Lemma 11.

Let $p$ be a point in $S$ and let $B$ be some axis-aligned box bounding $p$.
If $B$ is safe, then $p$ does not interact in $S$.

###### Proof.

Suppose without loss of generality that $p$ is red. Then $B$ is necessarily
red-safe (as it cannot be blue-safe). The point $p$ could only possibly
interact with a blue point $q$ lying in one of the quadrants. Because $q$ is
not in the corresponding minimal-set $S^{\prime}$ by definition of a red-safe
box, the box spanned by $p$ and $q$ contains a point of $S^{\prime}$. Thus $p$
and $q$ do not see each other in $S$. ∎

######  Lemma 12.

Let $p$ be a point in $S$ and let $B$ be some axis-aligned box. If $B$ is not
safe, then we can move $p$ inside $B$ to a position where it participates in
$S$.

###### Proof.

Suppose without loss of generality that $p$ is red. The box $B$ is not safe,
so in particular it is not red-safe. So either there is a blue point $q$ in
$cross(B)$ or there is a blue point $q$ on the corresponding minimal-set of
one of the quadrants of $B$. In the first case, we can move $p$ to a position
where it almost shares the same $x$ or $y$ coordinate as $q$ such $p$ and $q$
see each other (recall that no two points share the same $x$ or $y$
coordinate). In the second case, by moving $p$ right next to the corner of $B$
corresponding to the quadrant where $q$ lies, $p$ and $q$ will see each other
(recall that we assume no point of $S$ lies on the boundary of $B$ or its
quadrants). ∎

######  Lemma 13.

Let $p_{1},\ldots,p_{5}$ be points in $S$ of the same color and let $B$ be any
axis-aligned box. Then we can move these $5$ points inside $B$ such that
$p_{1}$ does not participate in $S$.

###### Proof.

We simply move $p_{2}$ close to $p_{1}$ such that it shields $p_{1}$ from
seeing any point of the opposite color lying in its upper right quadrant. We
shield off the other three corners similarly with $p_{3},p_{4}$ and $p_{5}$. ∎

######  Lemma 14.

Let $T$ be a rooted tree with $n$ nodes and let $c\in\mathbb{N}$ be an
integer. Consider a set of “chips” each associated to a single leaf in $T$ (a
leaf however can be associated to multiple chips). Place the chips on the
nodes of the tree such that every chip lies on the path from the root to its
associated leaf and every root to leaf path has at most $c$ chips on it. (Note
that multiple chips can be placed on the same node.) Then the sum $\Sigma$ of
the distance from chip to associated leaf over all chips is at most $c(n-1)$.

###### Proof.

We show the result by induction. For $n=1$ the result is trivially true.
Suppose it is true for all $1\leq n^{\prime}\leq n$, where $n\geq 1$ and
consider a rooted tree $T$ with $n+1$ nodes. We can choose to put $c_{r}\leq
c$ chips on the root. Each contributes at most $n-1$ to $\Sigma$, as any leaf
is at distance at most $n-1$ from the root. The remaining chips have to go in
the $k$ subtrees linked to the root, with respective numbers of nodes
$n_{1},n_{2}\ldots n_{k}$. Notice that since we already have $c_{r}$ chips on
the root, each root to leaf path in the $k$ subtrees can only have up to
$c-c_{r}$ chips. By our inductive hypothesis, the contribution of the
different subtrees to $\Sigma$ is at most
$(c-c_{r})(n_{1}-1)+(c-c_{r})(n_{2}-1)+\ldots(c-c_{r})(n_{k}-1)\leq(c-c_{r})(n_{1}+n_{2}+\ldots
n_{k})=(c-c_{r})(n-1)$. Together with the contribution from the chips on the
root we get $\Sigma\leq(c-c_{r})(n-1)+c_{r}(n-1)=c(n-1)$. By induction we
conclude the proof. ∎

We can now prove Theorem 10 with a proof similar to what can be found in [1].
In their case however, if a point can be moved anywhere inside a non-safe box
then the point can be moved in a way that changes the expected output of the
algorithm. In our case, we can do something similar by invoking Lemma 12 or
13, but this latter lemma requires use to be able to move multiple points of
the same color (but a constant number are enough). We can use Lemma 14 to show
that this does not impact the lower bound.

###### Proof of Theorem 10.

Consider a correct algorithm $A$ in the comparison-based model. We will
construct a respectful partition $\Pi$ of $S$ and “bad” permutation
$\sigma(S)$ such that $A$ is forced to do $\Omega(n({\cal H}(\Pi)+1))$
comparisons to solve the problem on $\sigma(S)$.

We will do this by having an adversary answer the queries issued by $A$
instead of letting $A$ query the input directly. The adversary will answer
queries in a way that forces $A$ to do many subsequent queries and is
consistent with some permutation $\sigma(S)$. Notice that as long as this
latter condition is satisfied, it makes no differences from the point of view
of $A$ if it is issuing queries to the adversary or querying $\sigma(S)$
directly.

Let $S_{\text{red}}$ be the set of red points in $S$ and $S_{\text{blue}}$ be
the set of blue points. First, we define two recursive partitionings on the
plane similar to kd-trees [4], one for the red points and one for the blue
points. We describe the structure for the red points. This structure will be
represented by a tree $\mathcal{T}_{\text{red}}$ of axis-aligned boxes,
constructed top to bottom. The root of $\mathcal{T}_{\text{red}}$ corresponds
to the entire plane. If $S_{\text{red}}$ is not safe, we split the points
around a vertical line $L$ such that the two open halfplanes defined by $L$
partition $S_{\text{red}}$ into two sets $S_{1}$ and $S_{2}$ of size at most
$\lceil|S_{\text{red}}|/2\rceil$. The children of the root will then
correspond to the two boxes thus defined. For every newly created node we
repeat the procedure, partitioning the set of points by median $x$ coordinates
at even levels of the tree and median $y$ coordinates at odd levels, until the
points contained are a safe subset of $S$ or a singleton, at which point we
define a leaf of $\mathcal{T}_{\text{red}}$. We define
$\mathcal{T}_{\text{blue}}$ similarly for the blue points. The partition
$\Pi_{\text{kd-tree}}$ of $S$ we consider is the one formed by the leaves of
$\mathcal{T}_{\text{red}}$ and $\mathcal{T}_{\text{blue}}$, which is
respectful by definition of the leaves.

The algorithm $A$ can issue queries to compare the $x$ or $y$ coordinate of
the points at indices $i$ and $j$. It knows which indices correspond to blue
points and which correspond to red. The adversary will map these indices to
boxes of $\mathcal{T}_{\text{red}}$ or $\mathcal{T}_{\text{blue}}$, depending
on their color. Additionally, if an index is mapped to a leaf box $B$, it will
also be assigned to a point in $S\cap B$ of the corresponding color. After
each query the adversary will update the mapping so that the query can be
resolved by knowing only this mapping, in a way that is consistent with all
previously answered queries. We let $n(B)$ denote the number of indices mapped
to $B$ or a descendant of $B$. Throughout the whole execution the adversary
maintains the invariant $\mathcal{I}$ that the number of indices mapped to
each point in $S$ is at most $1$ and for each box $B$ in
$\mathcal{T}_{\text{red}}$ (resp. $\mathcal{T}_{\text{blue}}$), $n(B)$ is at
most $|S_{\text{red}}\cap B|$ (resp. $|S_{\text{blue}}\cap B|$).

A box $B\in\mathcal{T}_{\text{red}}$ (resp. $B\in\mathcal{T}_{\text{blue}}$)
for which $n(B)=|S_{\text{red}}\cap B|$ (resp. $n(B)=|S_{\text{red}}\cap B|$)
is said to be full. We denote the box an index $i$ is mapped to as $B_{i}$. An
index $i$ mapped to an interior box is said to be floating. An index $i$
mapped to a leaf box is said to be fixed, and we denote the point it is
assigned to as $p_{i}$. A point in $S$ to which no index is assigned is said
to be free.

The adversary starts by mapping all red indices to the root of
$\mathcal{T}_{\text{red}}$ and all blue indices to the root of
$\mathcal{T}_{\text{blue}}$. Whenever an index $i$ is mapped to a leaf box
$B$, it is immediately assigned to a free point of the corresponding color in
$S\cap B$. This is always possible because of the invariant $\mathcal{I}$ we
maintain. When issued a query to compare, say, the $x$ coordinates of the
points at indices $i$ and $j$, the adversary proceeds as follows:

  1. 1.

If both indices $i$ and $j$ are fixed, then the adversary simply compares
$p_{i}$ and $p_{j}$ to answer the query.

  2. 2.

If either of the indices $i$ and $j$ is mapped to a non-leaf box $B$ which is
at an odd depth in $\mathcal{T}_{\text{red}}$ or $\mathcal{T}_{\text{blue}}$,
map it to one of the non-full children of $B$ and move on to the following
steps.

  3. 3.

Suppose that the indices $i$ and $j$ are both floating. Suppose further that
the vertical line separating the children of $B_{i}$ lies to the left of the
vertical line dividing the children of $B_{j}$ (otherwise, simply swap the
roles of $i$ and $j$). If the left child $B^{\ell}_{i}$ of $B_{i}$ and the
right child $B^{r}_{j}$ of $B_{j}$ are not full, the adversary maps $i$ to
$B^{\ell}_{i}$ and $j$ to $B^{r}_{j}$. The query can then be resolved and the
answer returned to $A$, as the $x$-coordinate of any point in $B^{\ell}_{i}$
is smaller than the $x$ coordinate of any point in $B^{r}_{j}$. If either
$B^{\ell}_{i}$ or $B^{r}_{j}$ is full, go to the next step.

  4. 4.

If, say, $B^{\ell}_{i}$ is full, then the adversary maps $i$ to the right
child $B^{r}_{i}$ of $B_{i}$. The comparison can not necessarily be resolved
at this point, so we go back to step 2.

If one of the indices $i$ or $j$ is fixed and the other is floating, then we
can easily adapt steps $2$, $3$ and $4$, by only ever updating the mapping of
the floating index.

Notice that in all these steps, the invariant $\mathcal{I}$ is maintained, as
it is impossible for the two children of $B_{i}$ (or $B_{j}$) to be full.
Otherwise, if $i$ is for example a red index, we would have $n(B_{i})\geq
n(B^{\ell}_{i})+n(B^{r}_{i})+1\geq|S_{\text{red}}\cap
B^{\ell}_{i}|+|S_{\text{red}}\cap B^{r}_{i}|+1=|S_{\text{red}}\cap B_{i}|+1$
(where the $+1$ term comes from the fact that at least one index is assigned
to $B_{i}$, namely $i$) and the invariant was violated to begin with.

We say that an increment occurs whenever the box to which an index is mapped
changes. Notice that every increment in the above procedure increase the depth
of $B_{i}$ by exactly one for some index $i$. Thus, by the end of execution,
the total number of increments is equal to the sum of the depths of the
$B_{i}$’s over all indices $i$. Call this sum $D$.

Let us show that if $T$ is the number of queries done by $A$, then
$T\in\Omega(D)$. We call the increments done in step $3$ ordinary increments.
We call increments done in step $4$ exceptional increments. Every query issued
by $A$ triggers $O(1)$ ordinary increments. To bound the number of exceptional
increments, notice that for every box $B$ (say in $\mathcal{T}_{\text{red}}$),
at least $\lfloor|S_{\text{red}}\cap B|/2\rfloor$ ordinary increments have to
occur at $B$ before any exceptional increment can occur, and that at most
$\lceil|S_{\text{red}}\cap B|/2\rceil$ exceptional increments can occur at $B$
after that point. So the total number of exceptional increments can be bounded
by the total number of ordinary increments, which is $O(T)$. The increments
done in step $2$ are either the direct results of a query or were preceded by
some unique exceptional query to which they can be charged, so their number is
also $O(T)$. Thus, the total number of increments $D$ is in $O(T)$, or in
other words, $T\in\Omega(D)$.

Next, notice that after the execution of $A$, if there is any index which is
mapped to an interior box $B$, we can arbitrarily remap it to one of the
children of $B$, then repeat the procedure until all indices are fixed. The
resulting mapping from indices to points defines a permutation $\sigma(S)$
consistent with all answers given to the queries by the adversary and which
maps red indices with red points, blue indices with blue points. Thus from the
point of view of $A$, we can consider it has queried $\sigma(S)$ directly. In
other words, the adversary did not “cheat”. Let $D_{\text{post}}$ be the sum
of the depth of $B^{\prime}_{i}$ over all indices $i$ after this post-
processing step. Every index is associated to a leaf and every leaf is full.
For any box $B$ in, say, $\mathcal{T}_{\text{red}}$ at depth $d$ we have
$|B\cap S_{\text{red}}|\geq\lfloor\frac{n}{2^{d}}\rfloor$, thus
$d\in\Omega(\log\frac{n}{|B\cap S_{\text{red}}|})$. It follows that

$\displaystyle D_{\text{post}}$
$\displaystyle\in\Omega\left(\mspace{-30.0mu}\sum_{\mspace{38.0mu}B\text{ leaf
in }\mathcal{T}_{\text{red}}}\mspace{-40.0mu}|B\cap
S_{\text{red}}|\log\frac{n}{|B\cap
S_{\text{red}}|}+\mspace{-30.0mu}\sum_{\mspace{38.0mu}B\text{ leaf in
}\mathcal{T}_{\text{blue}}}\mspace{-40.0mu}|B\cap
S_{\text{blue}}|\log\frac{n}{|B\cap S_{\text{blue}}|}\right)$
$\displaystyle=\Omega\left(\mspace{-30.0mu}\sum_{\mspace{38.0mu}S_{k}\in\Pi_{\text{kd-
tree}}}\mspace{-30.0mu}|S_{k}|\log\frac{n}{|S_{k}|}\right)$
$\displaystyle=\Omega(n{\cal H}(\Pi_{\text{kd-tree}})).$

It remains to prove a lower bound on $D$ using the lower bound we have on
$D_{\text{post}}$. We show that before the post-processing described in the
previous paragraph, for every root to leaf path in $\mathcal{T}_{\text{red}}$
or $\mathcal{T}_{\text{blue}}$, the number of indices mapped to an interior
box on the path is at most $4$. Indeed, suppose there was such a path in, say,
$\mathcal{T}_{\text{red}}$ with $5$ or more indices mapped to interior boxes.
Call these indices $i_{1},i_{2},\ldots,i_{5}$, and let $p_{1},\ldots,p_{5}$ be
the points they are associated with after post-processing. Notice that we can
freely move the point $p_{1}$ inside $B_{i_{1}}$ for example, without changing
the answer to any of the queries done by $A$. Let $B$ be the box of maximum
depth among $B_{i_{1}},\ldots,B_{i_{5}}$. Because all other boxes are
ancestors of $B$ in $\mathcal{T}_{\text{red}}$, they all contain $B$. Thus, we
can move all five points inside $B$ without changing the answer to any of the
queries done by $A$. Because $B$ is not safe we can apply either Lemma 12 or
Lemma 13 to move the points inside $B$ in a way that creates a new point set
$S^{\prime}$ with a different expected output. Then $A$ will not compute the
correct solution on $S^{\prime}$, which contradicts its definition as a
correct algorithm.

Now, for each index $i$ mapped to an interior node, place a “chip” on the
corresponding tree, at the node to which $i$ maps before post-processing.
Associate the chip with the leaf to which $i$ gets mapped after post-
processing. We know that every chip lies on the path from the root to its
associated leaf and that every root to leaf path in $\mathcal{T}_{\text{red}}$
or $\mathcal{T}_{\text{blue}}$ has at most $4$ chips on it. The sum of the
distance from chip to associated leaf over all chips is $D_{\text{post}}-D$.
By Lemma 14, we get $D_{\text{post}}-D\leq 4(n-1)$, that is, $D\geq
D_{\text{post}}-4(n-1)$. Thus,

$\displaystyle T$ $\displaystyle\in\Omega(D)$
$\displaystyle\subset\Omega(D_{\text{post}}-4n)$
$\displaystyle\subset\Omega(n{\cal H}(\Pi_{\text{kd-tree}})-4n)$
$\displaystyle\subset\Omega(n({\cal H}(\Pi_{\text{kd-tree}})-4)).$

Combined with the trivial $\Omega(n)$ bound we get a $\Omega(n({\cal
H}(\Pi_{\text{kd-tree}})+1))$ bound, which in turn implies a $\Omega(n({\cal
H}(S)+1))$ lower bound, as $\Pi_{\text{kd-tree}}$ is a respectful partition of
$S$. ∎

Notice that this lower bound implies the following:

######  Corollary 15.

For the problem of reporting participating points in the order-oblivious
comparison-based model, $\mbox{\rm OPT}(S)\in\Omega(h\log n)$, where $h$ is
the number of points which participate in $S$.

###### Proof.

Consider a respectful partition $\Pi$ of $S$. By definition of entropy we have
${\cal H}(\Pi)=\sum_{S_{k}\in\Pi}\frac{|S_{k}|}{n}\log\frac{n}{|S_{k}|}$. By
definition of a respectful partition and by Lemma 11, every point which
participates in $S$ will be in a singleton $S_{k}$. By summing only over these
$h$ points, we get $n{\cal H}(\Pi)\geq n\sum_{i=1}^{h}\frac{1}{n}\log n=h\log
n$. As this is true for any respectful partition, we have $n{\cal H}(S)\geq
h\log n$. ∎

This means in particular that if we can report all points which participate in
$S$ in $O(n({\cal H}(S)+1))$ time, then we can afford to run an algorithm in
worst case optimal $O(h\log h+j)$ time on these reported points to compute the
$j$ red-blue pairs which see each other. The resulting algorithm will be
instance-optimal in the order-oblivious model.

##  4 Instance optimal comparison-based algorithm in the order-oblivious
setting

In this section we present a comparison-based algorithm for reporting
participating points with a runtime matching the lower bound we saw in the
previous section (note that worst-case optimal $\mathcal{O}(n\log n+h)$
algorithms are easy to obtain by the method of [11]). Once again, the main
algorithm will be very similar to what is done in [1], however their results
do not directly apply here. The main difficulty in adapting their algorithm to
our case is that the relation we consider here is not decomposable. More
precisely, if we know that some point $p$ does or does not participate in
$S^{\prime}$ and $S^{\prime\prime}$, we cannot use this to decide if $p$
participates in $S^{\prime}\cup S^{\prime\prime}$. The bulk of the work here
will thus be to preprocess the set $S$ in order to make the safety tests
decomposable, while keeping our preprocessing time within $O(n({\cal
H}(S)+1))$.

###  4.1 The main algorithm

Before we go into detail about how to preprocess the points let us see how, if
we can build the right data structure, we can use it to report the
participating points in $S$ in $O(n({\cal H}(S)+1))$ time. We will need the
following definition and easy observations:

######  Definition 16.

Let $S$ be a set of red and blue points. A subset $S^{\prime}\subset S$
_conforms with $S$_ if it contains all points which participate in $S$.

######  Observation 17.

Let $S$ be a set of of red and blue points and let $S^{\prime}$ be a subset
which conforms with $S$. Then an axis-aligned box is safe for $S$ if and only
if it is safe for $S^{\prime}$. Moreover, a point participates in $S$ if and
only if it participates in $S^{\prime}$.

######  Observation 18.

If $B$ is a safe box for $S$, then any sub-box of $B$ is safe for $S$.

We have the following algorithm and theorem, adapted from [1], where $\delta$
is a constant to be chosen later:

Input: A point set $S$ of size $n$

1 Set $Q=S$.

2 for  _$j=0,1,\ldots\lfloor\log(\delta\log n)\rfloor$_ do

3 Partition the points in $Q$ using a kd-tree to get $r_{j}=2^{2^{j}}$ subsets
$Q_{1},\ldots,Q_{r_{j}}$ of size at most $\lceil|Q|/r_{j}\rceil$, along with
corresponding bounding boxes $B_{1},\ldots,B_{r_{j}}$.

4 for  _$i=0,1,\ldots,r_{j}$_ do

5 if  _$B_{i}$ is safe for $Q$_ then

6 Prune all points in $Q_{i}$ from $Q$.

7

8

9

10Solve the reporting problem for the remaining set $Q$ directly in
$O(|Q|\log|Q|)$ time.

11

Algorithm 1 Reporting participating points

######  Theorem 19.

Let $S$ be a set of $n$ points in general position. Suppose we have
preprocessed $S$ such that for any subset $S^{\prime}\subset S$ containing all
points which participate in $S$ we can test if an axis-aligned box is safe for
$S^{\prime}$ in $O(n^{1-\alpha})$ time, plus the cost of a constant number of
range-emptiness queries on $S^{\prime}$.
Then Algorithm 1 can report all points which participate in $S$ in $O(n({\cal
H}(S)+1))$ time.

We reiterate the proof for the sake of completeness and to underline how
Observation 17 and our additional assumptions on preprocessing factor into it:

###### Proof.

By Observation 17 and Lemma 11, we only ever prune points which do not
participate in the original set $S$ and we never modify which points
participate among those that remain. Thus the algorithm invoked at line $6$
will compute the correct output.

By assumption, testing a box for safety in $Q$ can be done in
$O(n^{1-\alpha})$ time plus the cost of a constant number of range-emptiness
queries on $Q$. Using a simple and ingenious trick by T. Chan [8], we can
perform $r$ orthogonal range emptiness queries on a set of size $m$ in
$O(m\log r+r^{O(1)})$ time. Thus, the $r_{j}$ tests of lines $3$ and $4$ can
be done in $O(|Q|\log r_{j}+r_{j}^{O(1)}+r_{j}n^{1-\alpha})$ time. As
$r_{j}<n^{\delta}$, by taking $\delta$ small enough the
$r_{j}^{O(1)}+r_{j}n^{1-\alpha}$ term can be made sublinear. As the outer loop
of the algorithm is only executed $O(\log(\log n))$ times the total
contribution of these terms over the whole algorithm can also be made
sublinear and thus negligible. Line 2 can be done in $O(|Q|\log r_{j})$ time
by the classical recursive algorithm to compute kd-trees.

Now let $n_{j}$ be the number of points in $Q$ just after iteration $j$. The
runtime of the algorithm is in $O(\sum_{j}n_{j}\log r_{j+1})$. This includes
the final step at line $6$, as for $j=\lfloor\log(\delta\log n)\rfloor$ (i.e.
after the last iteration of the outer loop) we have $O(|Q|\log|Q|)\subset
O(n_{j}\log n^{2\delta})=O(n_{j}\log r_{j+1})$. Let $\Pi$ be a respectful
partition of $S$ and consider $S_{k}\in\Pi$. At iteration $j$ all subsets
$Q_{i}$ lying entirely inside the bounding box of $S_{k}$ are pruned by
Observation 18. Since the bounding box of $S_{k}$ intersects at most
$O(\sqrt{r_{j}})$ cells of the kd-tree, the number of points in $S_{k}$
remaining after iteration $j$ is $min\\{|S_{k}|,O(\sqrt{r_{j}}\cdot
n/r_{j})\\}$ = $min\\{|S_{k}|,O(n/\sqrt{r_{j}})\\}$. The $S_{k}$’s cover the
entire point set so by double summation we have:

$\displaystyle\sum_{j}n_{j}\log r_{j+1}$
$\displaystyle\leq\sum_{j}\sum_{k}\min\left\\{|S_{k}|,O\left(n/\sqrt{2^{2^{j}}}\right)\right\\}\cdot
2^{j+1}$
$\displaystyle=\sum_{k}\sum_{j}\min\left\\{|S_{k}|,O\left(n/2^{2^{j-1}}\right)\right\\}\cdot
2^{j+1}$ $\displaystyle\in
O\left(\sum_{k}\mspace{-50.0mu}\sum_{\mspace{70.0mu}j\leq\log(2\log(n/|S_{k}|))}\mspace{-70.0mu}|S_{k}|\cdot
2^{j}\mspace{10.0mu}+\mspace{-60.0mu}\sum_{\mspace{70.0mu}j>\log(2\log(n/|S_{k}|))}\mspace{-70.0mu}n\cdot
2^{j}/2^{2^{j-1}}\right)$ $\displaystyle\in
O\left(\sum_{k}|S_{k}|(\log(n/|S_{k}|)+1)\right)=O(n({\cal H}(S)+1)).\qed$

###  4.2 Cross-safety tree

Figure 4: A cell of red points and the corresponding box $B$. The relevant
points are indicated by arrows. The box point is indicated by a cross.

In order to solve our problem instance-optimally (in the order-oblivious
comparison-based model), we want to design a data-structure which allows us to
quickly test if a given axis aligned box $B$ is safe for $S$. To make the
presentation clearer, we focus on testing if $B$ is red-cross-safe and the NE-
minimal-set of $\mbox{\rm NE}(B)\cap S$ is red. This can then be repeated
symmetrically for $\mbox{\rm NW}(B),\mbox{\rm SE}(B)$ and $\mbox{\rm SW}(B)$
to test if $B$ is red-safe (and similarly for testing if $B$ is blue-safe). We
will see how to build and query the following data structure:

######  Definition 20.

A _cross-safety tree $T_{S}$ on $S$_ is a recursive partitioning on the plane
similar to a kd-tree where we stop subdividing the points once we have reached
a cross-safe subset of points. The root of $\mathcal{T}_{\text{red}}$
corresponds to $S$. If $S$ is not cross-safe, we split the points around a
vertical line $L$ such that the two open halfplanes defined by $L$ partition
$S$ into two sets $S_{1}$ and $S_{2}$ of size at most $\lceil|S|/2\rceil$. The
children of the root will then correspond to $S_{1}$ and $S_{2}$. For every
newly created node we repeat the procedure, partitioning the set of points by
median $x$ coordinates at even levels of the tree and median $y$ coordinates
at odd levels, until the points contained are a cross-safe subset of $S$.

The _cell_ of a point $p$, denoted as $C_{p}$ is the the subset of points
contained in the same leaf as $p$. A cell of $T_{S}$ is red (resp. blue) if
the points it contains are red (resp. blue).

The _box of a point $p$_, denoted as $B_{p}$ is the smallest axis-aligned box
containing all points in $C_{p}$ (slightly extended to enforce our assumption
of only considering boxes for which there are no points on the boundary of
their four quadrants). A box of $T_{S}$ is red (resp. blue) if the points it
contains are red (resp. blue).

The _box-point of $p$_ is the top-right point of the box of $p$, and has the
same color as $p$.

A point is _relevant_ if it has the minimum $x$ or $y$ coordinate among all
points in its box (or equivalently, in its cell).

(See fig. 4 for an illustration of these definitions.)

Each node $u$ in the tree stores:

  * •

The set of point it contains, which we denote as $P_{u}$.

  * •

The smallest axis-aligned bounding box of $P_{u}$, which we denote as $B_{u}$.

  * •

The red box-points of minimum $x$ and $y$ coordinates among all box-points
associated with a red point in $P_{u}$.

  * •

The subset of all relevant blue points in the minimal set of $P_{u}$, sorted
by $x$-coordinate.

Note that if the points in a minimal set are sorted by $x$ coordinate then
they are also sorted (in reverse order) by $y$ coordinate.

###  4.3 Querying a cross-safety tree

Before we see how to build a cross-safety tree on $S$ efficiently, let us see
how we make queries on a node $u$ of $T_{S}$. A query consists of a lower
range $R_{L}=[x_{L},+\infty]\times[y_{L},+\infty]$ and an upper range
$R_{U}=[-\infty,x_{U}]\times[-\infty,y_{U}]$ such that $R_{L}\cap
R_{U}\neq\emptyset$ and neither the boundaries of $R_{L}$ nor $R_{U}$
intersect any blue box of $T_{S}$. It returns:

  * •

$rx_{u}$, the minimum $x$-coordinate of any red box-points associated with a
red point in $P_{u}\cap R_{L}$ (set to $+\infty$ if there are no red points in
$P_{u}\cap R_{L}$).

  * •

$ry_{u}$, the minimum $y$-coordinate of any red box-points associated with a
red point in $P_{u}\cap R_{L}$ (set to $+\infty$ if there are no red points in
$P_{u}\cap R_{L}$).

  * •

$bx_{u}$, the minimum $x$-coordinate of any blue points in the minimal set of
$P_{u}\cap R_{L}\cap R_{U}$ (set to $+\infty$ if there are no blue points in
the minimal set of $P_{u}\cap R_{L}\cap R_{U}$).

  * •

$by_{u}$, the minimum $y$-coordinate of any blue points in the minimal set of
$P_{u}\cap R_{L}\cap R_{U}$ (set to $+\infty$ if there are no blue points in
the minimal set of $P_{u}\cap R_{L}\cap R_{U}$).

Observe the following:

######  Observation 21.

If a horizontal or vertical line passes through a red point then it does not
intersect any blue-cross-safe box. The same applies when “red” and “blue” are
swapped.

######  Observation 22.

Let $B$ be a red-cross-safe box. Then all points in $B$ dominate (resp. are
dominated by) the same subset of blue points in $S$. The same applies when
“red” and “blue” are swapped.

We will need a few additional lemmas.

######  Lemma 23.

The points corresponding to $bx_{u}$ and $by_{u}$ are relevant points of
$T_{S}$.

###### Proof.

Let $P=P_{u}\cap R_{L}\cap R_{U}$, and suppose there is a blue point on the
minimal set of $P$. Let $p$ be the leftmost point in $P$ which does not
dominate any red point in $P$. Suppose that $bx_{u}$ is not equal to $x(p)$.
The only way this can happen is if $p$ is not on the minimal set of $P$,
meaning that there is a blue point $q$ which is dominated by $p$ (as $p$ does
not dominate any red point). In particular, $q$ lies to the left of $p$. By
definition of $p$, $q$ thus dominates a red point. But if $q$ dominates a red
point and $p$ dominates $q$, then $p$ dominates a red point, which contradicts
the definition of $p$. Thus $bx_{u}=x(p)$. Moreover, if $p$ does not dominate
any red point, then no point in its box dominates a red point, as the box is
blue-cross-safe. Because the boundaries of $R_{L}$ and $R_{U}$ do not
intersect any blue box, the whole box of $p$ is contained in $P$. Thus, by
definition of $p$, it is the leftmost point in its box and it is relevant. The
same reasoning shows that $by_{u}$ is the $y$ coordinate of a relevant point.
∎

######  Lemma 24.

If the bounding box $B_{u}$ of points in $P_{u}$ lies entirely in $R_{L}$,
then we can return the necessary information in $O(\log n)$ time.

###### Proof.

In this case, $rx_{u}$ and $ry_{u}$ are already stored in the node, so we can
return them in constant time. By Lemma 23, the point giving $bx_{u}$ is the
relevant blue point with minimum $x$ coordinate among all blue points in the
minimal set of $P_{u}\cap R_{U}$. This is also the relevant blue point with
maximum $y$ coordinate among all blue points in the minimal set of $P_{u}\cap
R_{U}$.

We can do a binary search through the relevant blue points in the minimal set
of $P_{u}$ to find the point $p$ below the line $y=y_{U}$ with maximum $y$
coordinate. If this point is not in $R_{U}$ (because $x(p)>x_{U}$) then no
relevant blue point in the minimal set of $P_{u}$ is in $R_{U}$, as all other
relevant blue points $q$ in the minimal set of $P_{u}$ with $y(q)\leq y_{U}$
will have $x(q)>x(p)>x_{U}$. In this case we set $bx_{u}$ to $+\infty$.
Otherwise $bx_{u}=x(p)$.

We can find $by_{u}$ similarly with a single binary search. ∎

######  Lemma 25.

If $u$ is not a leaf of $T_{S}$ and $B_{u}$ intersects the boundary of
$R_{L}$, then we can return the necessary information after querying the
children of $u$ with the same lower range $R_{L}$ (but possibly different
upper ranges) and a constant amount of additional work.

###### Proof.

Suppose without loss of generality that the children of $u$ split $P_{u}$ by a
vertical line (the situation for a horizontal line is similar). Let $v$ be the
child corresponding to the left half-plane and $w$ the one corresponding to
the right half-plane. Let us focus on computing $bx_{u}$, as this is the one
requiring the most care.

Querying $v$ with the same $R_{L}$ and $R_{U}$ returns some values $rx_{v}$,
$ry_{v}$, $bx_{v}$ and $by_{v}$. A blue point $p$ on the minimal set of
$P_{w}\cap R_{L}\cap R_{U}$ is a blue point on the minimal set of $P_{u}\cap
R_{L}\cap R_{U}$ if and only if $y(p)\leq by_{v}$ and $p$ does not dominate
any red point in $P_{v}\cap R_{U}$. By Observation 22 this is equivalent to
saying that $y(p)\leq by_{v}$ and $y(p)\leq ry_{v}$.

Thus we can compute $bx_{u}$ by setting
$R^{\prime}_{U}=[-\infty,x_{U}]\times[-\infty,\min\\{y_{U},ry_{v}\\}]$,
querying $w$ with $R_{L}$ and $R^{\prime}_{U}$ to get values $rx_{w}$,
$ry_{w}$, $bx_{w}$ and $by_{w}$, then setting
$bx_{u}=\min\\{bx_{v},bx_{w}\\}$. Notice that by Observation 21, we are
allowed to query $w$ with $R^{\prime}_{U}$ as its boundary does not intersect
any blue box of $T_{S}$. It is then easy to see that
$rx_{u}=\min\\{rx_{v},rx_{w}\\}$, $ry_{u}=\min\\{ry_{v},ry_{w}\\}$ and
$by_{u}=\min\\{by_{v},by_{w}\\}$. ∎

######  Lemma 26.

If $u$ is a leaf of $T_{S}$ and $B_{u}$ intersects the lower boundary or the
left boundary of $R_{L}$ but not both simultaneously, then we can return the
necessary information in constant time.

###### Proof.

In this case, we know that $B_{u}$ is a red box, as by assumption the boundary
of $R_{L}$ does not intersect any blue box of $T_{S}$. Thus $B_{u}$ contains
no blue points and we know $bx_{w}=by_{w}=+\infty$. Suppose without loss of
generality that $B_{u}$ intersects the left boundary of $R_{L}$. Then the
rightmost point of $B_{u}$ is in $R_{L}$, and thus $P_{u}\cap R_{L}$ is non-
empty. Because all points in $P_{u}$ have the same box-point
$p=(p_{x},p_{y})$, we have $rx_{u}=p_{x}$ and $ry_{u}=p_{y}$. ∎

######  Lemma 27.

If $u$ is a leaf of $T_{S}$ and $B_{u}$ intersects both the lower boundary and
the left boundary of $R_{L}$, then we can return the necessary information
after a single orthogonal range-emptiness test.

###### Proof.

Again, we know that $B_{u}$ is a red box and all points in $P_{u}$ have the
same box point $p=(p_{x},p_{y})$. To know if we need to set
$rx_{u}=ry_{u}=+\infty$ or $rx_{u}=p_{x}$ and $ry_{u}=p_{y}$, we simply need
to test if there is a (necessarily red) point in $B_{u}\cap R_{L}$. This
requires a single range-emptiness test. ∎

By applying the relevant result among Lemmas 24, 25, 26 and 27 recursively we
get:

######  Theorem 28.

We can query the root of a cross-safety tree $T_{S}$ in $O(\sqrt{n}\log n)$
time plus the cost of a single range-emptiness test.

As a corollary, we get:

######  Corollary 29.

Let $B$ be an axis aligned box. We can query a cross-safety tree $T_{S}$ to
test if $B$ is red-NE-safe for $S$ in $O(\sqrt{n}\log n)$ time plus the cost
of a constant number of orthogonal range-emptiness tests on $S$.

###### Proof.

With two orthogonal range-emptiness queries on the blue points of $S$ and one
on the red points of $S$ we can test if $B$ contains at least one red point
and $\mbox{\rm cross}(B)$ contains only red points (that is, test if $B$ is
red-cross-safe for $S$). If $B$ is not red-cross-safe for $S$ we can
immediately return “No”. We assume from now on that it is.

Let $R_{L}$ be the range corresponding to $\mbox{\rm NE}(B)$, and let
$R_{U}=[-\infty,+\infty]\times[-\infty,+\infty]$. Because $R$ is red-cross-
safe, it is easy to see that the boundary of $R_{L}$ does not intersect any
blue box of $T_{S}$ (this is also trivially true for $R_{U}$). Thus, we can
query the root $u$ of $T_{S}$ with $R_{L}$ and $R_{U}$ to get the $x$
coordinate $bx_{u}$ of the blue point with minimum $x$ coordinate among all
blue points on the minimal set of $\mbox{\rm NE}(B)\cap S$, or $+\infty$ if no
such point exists. In particular, this allows us to test if such a point
exists. ∎

We also have the following:

######  Lemma 30.

Let $S^{\prime}\subset S$ be a subset which conforms with $S$ and let $B$ be
an axis-aligned box. If $S^{\prime}\cap B\neq\emptyset$, then we can replace
all orthogonal range-emptiness tests on $S$ with the same tests on
$S^{\prime}$ in the procedure described in Corollary 29 (including the tests
done while querying $T_{S}$) without affecting the outcome.

###### Proof.

If there are both red and blue points in $S\cap\mbox{\rm cross}(B)$, then at
least one of these blue points participates in $S$. Because $S^{\prime}$
conforms with $S$, this blue point is also in $S^{\prime}$, so $S^{\prime}$ is
not red-cross-safe. The converse is trivially true. Thus, the initial three
range-emptiness tests return the same results on $S$ and $S^{\prime}$.

Now consider the query done on $T_{S}$. If the corner of the lower range
$R_{L}$ does not intersect a red leaf box of $T_{S}$, then no range-emptiness
test is performed and the claim holds. Now suppose $R_{L}$ intersects a red
leaf box $B$ of $T_{S}$. Let $S^{\prime\prime}$ be the set of points in $S$
where we remove all points in $S\cap B\cap R_{L}$ which are not in
$S^{\prime}\cap B\cap R_{L}$. Notice that by replacing the range-emptiness
query on $S$ with one on $S^{\prime}$, the procedure behave exactly like
querying a cross-safety tree on $S^{\prime\prime}$. Because $S^{\prime}\subset
S^{\prime\prime}\subset S$ we know that $S^{\prime\prime}$ conforms with $S$
and thus by Observation 17 the claim holds. ∎

Thus, this data-structure fits the prerequisites of Theorem 19, and we can use
it to get an algorithm solving the problem in $O(n({\cal H}(S)+1))$ time after
having built it. The only missing ingredient to get an instance-optimal
algorithm is building the data-structure within the same asymptotic runtime.
We show in the following section that we can indeed do this.

###  4.4 Construction in $O(n({\cal H}(S)+1))$ time

Rather than focusing on constructing the cross-safety tree specifically, we
start with a bit more general setting.

######  Theorem 31.

Let $S$ be a set of points. Let $C$ be a property on axis-aligned bounding
boxes of the plane such that for boxes $B_{2}\subset B_{1}$, if $C(B_{1})$ is
true then $C(B_{2})$ is true. (Note that $C$ can depend on $S$).

A partition $\Pi$ of $S$ is $C$-respectful if every set in $\Pi$ is a
singleton or can be enclosed by an axis aligned bounding box $B$ such that
$C(B)$ is true.

Let ${\cal H}_{C}(S)$ be the minimum of ${\cal H}(\Pi)$ over all
$C$-respectful partitions of $S$.

If property $C(B)$ can be tested in $O(|S\cap B|)$ time when given access to
$S\cap B$, then a kd-tree $T_{S}^{C}$ with stopping condition $C$ on the
leaves can be built in $O(n({\cal H}_{C}(S)+1))$ time.

This remains true if for each node in the tree we do an additional linear
amount of work (in the number of points considered at that node).

The proof is similar in spirit to that of Theorem 19, although simpler.

###### Proof.

Consider the classical top-down recursive approach to construct a kd-tree on
$S$ (with linear-time median, selection), where we stop subdividing points
once we have reached a bounding-box $B$ with property $C$. Consider any
$C$-respectful partition $\Pi$ of $S$. Let $S_{k}\in\Pi$ and let $B_{k}$ be a
corresponding bounding box with the property $C$. At the $j$’th level of the
recursion, we have partitioned the plane into $O(2^{j})$ boxes each containing
at most $\left\lceil n/2^{j}\right\rceil$ points still to be considered. Any
box $B$ of $T_{S}^{C}$ which is entirely contained in $B_{k}$ has property $C$
and can be set as a leaf. In other words the box $B$ does not need to be
recursed on and the points in $B\cap S$ are not considered at level $j$ or
lower. Because $B_{k}$ intersects at most $O(\sqrt{2^{j}})$ boxes of
$T_{S}^{C}$ at level $j$, the number of points in $S_{k}$ to consider at level
$j$ is $min\\{|S_{k}|,O(\sqrt{2^{j}}\cdot n/2^{j})\\}$ =
$min\\{|S_{k}|,O(n/\sqrt{2^{j}})\\}$. At each level, the amount of work to be
done is linear in the number of points to consider. The $S_{k}$’s cover the
entire point set so by double summation we get that the runtime is in

$\displaystyle
O\left(\sum_{j}\sum_{k}\min\left\\{|S_{k}|,n/\sqrt{2^{j}}\right\\}\right)$
$\displaystyle=O\left(\sum_{k}\sum_{j}\min\left\\{|S_{k}|,n/\sqrt{2^{j}}\right\\}\right)$
$\displaystyle=O\left(\sum_{k}\mspace{-20.0mu}\sum_{\mspace{30.0mu}j\leq
2\log(n/|S_{k}|)}\mspace{-30.0mu}|S_{k}|\mspace{10.0mu}+\mspace{-30.0mu}\sum_{\mspace{30.0mu}j>2\log(n/|S_{k}|)}\mspace{-30.0mu}n/\sqrt{2^{j}}\right)$
$\displaystyle=O\left(\sum_{k}|S_{k}|(\log(n/|S_{k}|)+1)\right)$
$\displaystyle\subset O\left(n({\cal H}_{C}(S)+1)\right).\qed$

Note that the proof generalizes easily to any constant dimension $d>0$. We can
apply this theorem to get the following:

######  Lemma 32.

A set of points $S$ can be preprocessed in $O(n({\cal H}(S)+1))$ time so that
for any subset $S_{k}\subset S$, we can test if all points in $S_{k}$ lie in a
common vertical slab containing only points of $S$ of the same color in
$O(S_{k})$ time.

###### Proof.

Let $u$ be the root of $T_{S}$. To query $u$ we simply apply the relevant
result among Lemmas 24, 25, 26 and 27 and then apply them recursively to the
children when needed.

Notice that when doing so, the only nodes we visit are the root, the nodes
with a bounding box intersecting the boundary of $R_{L}$ and their children
(and $R_{L}$ never changes during execution). It is a well known result that
in a (median-split) kd-tree this number is $O(\sqrt{n})$ (and $T_{S}$ is a
subtree of such a kd-tree). For each of these visited nodes, we do at most
$O(\log n)$ amount of work, except if it is a leaf whose bounding box
intersects both the left and lower boundary of $R_{L}$. In this case we do a
range-emptiness test. Notice that there is at most one leaf of $T_{S}$ for
which this is the case, so this can only happen once. ∎

Which in turn implies:

######  Theorem 33.

A cross-safety tree on $S$ can be constructed in $O(n({\cal H}(S)+1))$.

###### Proof.

Start by projecting all points in $S$ on the horizontal line $y=0$ to get a
new set of points $S^{\prime}$. Apply the previous theorem in 1 dimension with
the property $C(I)$ being “all points of $S^{\prime}$ in the interval $I$ are
of the same color”. This requires $O(n({\cal H}_{C}(S^{\prime})+1))$ time. It
is easy to see that with the constructed data-structure we can assign to each
point the maximal monochromatic interval that contains it in linear time. Then
we can test if all points in $S_{k}$ lie in a common vertical slab containing
only points of $S$ of the same color in $O(S_{k})$ time. Moreover, because all
points in a safe subset of $S$ lie in such a vertical slab, we have ${\cal
H}_{C}(S^{\prime})\leq{\cal H}(S)$ and so the claim holds. ∎

Finally, putting this together with 30 and Theorem 19 we get the main result.

######  Theorem 34.

All points participating in $S$ can be reported in $O(n({\cal H}(S)+1))$ time.
In other words, there is an instance-optimal algorithm for this problem in the
order-oblivious comparison-based model.

###### Proof.

Call $C(B)$ the property “$B$ is a cross-safe axis-aligned box”. Using the
previous lemma (and the analogous result for horizontal slabs), we can
preprocess $S$ in $O(n({\cal H}(S)+1))$ such that property $C(B)$ can be
tested in $O(|B\cap S|)$ when given access to $B\cap S$. Notice also that when
constructing a cross-safety tree $T_{S}$ on $S$, all information to be stored
at a node $u$ can be computed in $O(|B_{u}\cap S|)$ time (using the
information stored in the children in case of an interior node). Thus we can
apply Theorem 31 to construct $T_{S}$ in $O(n({\cal H}_{C}(S)+1))$. As every
safe box is also cross-safe, we have ${\cal H}_{C}(S)\leq{\cal H}(S)$, which
concludes the proof. ∎

One thing to note here is that while this guarantees that the algorithm is
optimal with respect to any parameter of the instance which does not depend on
the order of the input points, it is not immediately obvious that it runs in
$O(n\log h)$ time, where $h$ is the number of points to report (we only know
that if there is an algorithm in the comparison-based model running within
this time bound, then so does ours). The following theorem proves this fact.

######  Theorem 35.

Let $S$ be an instance of the Reporting participating points problem and let
$h$ be the number of points which participate in $S$. Then $n({\cal
H}(S)+1)\in O(n\log h)$.

###### Proof.

We prove this by showing that there is a respectful partition $\Pi$ of $S$
such that $n({\cal H}(\Pi)+1)\in O(n\log h)$. By definition of ${\cal H}(S)$
the claim then holds.

We define $h+1$ vertical slabs $V_{1},V_{2},\ldots,V_{h+1}$ of the plane as
follows.

  * •

Let $\varepsilon>0$ be a constant smaller than the difference in $x$
coordinates between any two distinct points in $S$.

  * •

Let $p_{1},p_{2},\ldots,p_{h}$ be the points participating in $S$, ordered by
$x$ coordinate.

  * •

Let $H_{1}$ be the set of points in the plane with $x$ coordinate at most
$x(p_{1})-\varepsilon$. Let $H_{h+1}$ be the set of points in the plane with
$x$ coordinate at least $x(p_{h})+\varepsilon$.

  * •

For $1<i<h+1$, let $H_{i}$ be the set of points in the plane with $x$
coordinate between $x(p_{i-1})+\varepsilon$ and $x(p_{i})-\varepsilon$.

We define $h+1$ horizontal slabs $V_{1},V_{2},\ldots,V_{h+1}$ similarly by
ordering the participating point by $y$ coordinate.

The pairwise intersections of these slabs define $(h+1)^{2}$ disjoint axis-
aligned boxes. We let $B_{1},B_{2},\ldots,B_{k}$ be the set of such boxes
which contain at least one point of $S$ (which is necessarily non-
participating). It is clear that $k\leq\min\\{n-h,(h+1)^{2}\\}$. Moreover, for
any $1\leq i\leq k$, the box $B_{i}$ is safe. Indeed, all points in
$cross(B_{i})$ are of the same color, otherwise at least one of these points
would participate in $S$, which contradicts the definition of $B_{i}$. Without
loss of generality, suppose this color is red. Now, suppose there was a blue
point $b$ on, say, the NE-minimal-set of $S\cap\mbox{\rm NE}(B_{i})$. Then,
because all points in $cross(B_{i})$ are red and do not participate in $S$,
the box spanned by $b$ and the lower-left corner of $B_{i}$ contains no point
of $S$. This contradicts the fact that $B_{i}$ contains a point of $S$ by
definition. Thus there is no blue point on the NE-minimal-set of
$S\cap\mbox{\rm NE}(B_{i})$ (and similarly for the three other quadrants of
$B_{i}$). So $B_{i}$ is safe. For all $1\leq i\leq k$, we define $S_{i}=S\cap
B_{i}$.

The partition we consider is $\Pi=\\{S_{i}\mid 1\leq i\leq
k\\}\cup\\{\\{p\\}\mid p\text{ participates in }S\\}.$ It is respectful by the
previous discussion. We have

$\displaystyle{\cal H}(\Pi)$
$\displaystyle=\sum_{i=1}^{k}\frac{|S_{i}|}{n}\log\frac{n}{|S_{i}|}+\sum_{p\text{
participates in }S}\frac{1}{n}\log n$
$\displaystyle=\sum_{i=1}^{k}\frac{|S_{i}|}{n}\log\frac{n}{|S_{i}|}+\frac{h}{n}\log
n.$

The first term in this sum is maximized when the non-participating points are
fairly divided between the $k$ different sets $S_{i}$ (by the concavity of the
considered function). Moreover, because $k\leq\min\\{n-h,(h+1)^{2}\\}$, we
have $\frac{n-h}{kn}\log\frac{nk}{n-h}\in O(\frac{1}{k}\log h)$. Thus

$\displaystyle{\cal H}(\Pi)$
$\displaystyle\leq\sum_{i=1}^{k}\frac{(n-h)/k}{n}\log\frac{n}{(n-h)/k}+\frac{h}{n}\log
n$ $\displaystyle\in O\left(\sum_{i=1}^{k}\frac{1}{k}\log h+\frac{h}{n}\log
n\right)$ $\displaystyle=O(\log h+\frac{h}{n}\log n).$

Because $h\log n\in O(n\log h)$ we finally get

$\displaystyle n({\cal H}(\Pi)+1)$ $\displaystyle\in O(n\log h+h\log n+n)$
$\displaystyle\subset O(n\log h).$

This concludes the proof. ∎

##  5 Instance-optimality is impossible with linear queries

In the previous section, we have shown that there is a comparison-based
algorithm to report participating points which is instance-optimal in the
order-oblivious runtime against all comparision-based algorithm solving the
problem. We also show that if we “compete” against algorithms which can do
queries of the form $x(p)-x(q)\geq y(p)-y(q)$, then such a result is no longer
possible, even if we allow our algorithm to be in a much stronger model of
computation.

Figure 5: Example of an instance in $D$.

######  Proposition 36.

Let $\mathcal{A}$ be the class of algorithms in the real RAM model which only
access the input through comparison of coordinates and queries of the form
$x(p)-x(q)\geq y(p)-y(q)$. For the problem of reporting participating points
in the order-oblivious setting, there is no algebraic computation tree $A$
such that $T_{A}(S)\leq O(1)T_{A^{\prime}}(S)$ for every instance $S$ and
every correct algorithm $A^{\prime}\in\mathcal{A}$.

In other words, no algebraic computation tree can perform within a constant
factor of complexity against every (correct) algorithm in $\mathcal{A}$ on
every input.

###### Proof.

Consider the set of instances $D$ with the following structure: We have three
lines $L_{1}$, $L_{2}$, $L_{3}$ with slope $-1$ where $L_{1}$ is above $L_{2}$
and $L_{2}$ is above $L_{3}$. There are $n$ distinct red points on $L_{1}$,
$n$ distinct blue points on $L_{2}$. On $L_{3}$ there is a red and a blue
point such that their $x$ and $y$ coordinates are smaller than the $x$ and $y$
coordinates of any of the points on $L_{1}$ and $L_{2}$. Finally, there is an
additional red point $p$ which dominates all others. See Figure 5 for an
example.

This configuration can be detected in linear time by an algorithm in
$\mathcal{A}$. It is easy to see that when an instance is in this
configuration, every point needs to be reported with the possible exception of
$p$. Consider an instance $I$ where $p$ needs to be reported. Then there is a
blue point $q$ which is rectangular-visible from $p$. Let us call $r$ the rank
of $q$ in $I$ with respect to the order of $x$-coordinates. There is also an
algorithm $A_{r}\in\mathcal{A}$ which can do the following.

  * •

First, detect if the instance is in $D$ in linear time.

  * •

If the instance is in $D$, find the point $q$ of rank $r$ by a linear-time
selection algorithm.

  * •

Test in linear time if $q$ is blue and $p$ is visible from $q$.

  * •

If this is the case, output all points.

  * •

If any of the tests above fail, return the correct output by brute-force in
$O(n^{3})$ time.

The algorithm $A_{r}$ is correct on every instance and runs in linear time on
any permutation of instance $I$ (thus it runs in linear time on $I$ in the
order-oblivious setting). There is such an algorithm for every instance in
$D$.

On the other hand, there is no algebraic computation tree which can solve all
instances in $D$ where $p$ needs to be reported in linear time. To see this,
we can relax the problem to ”Is $p$ rectangular visible from some blue point?”
and restrict the inputs even more to a set $D^{\prime}\subset D$. We now
restrict inputs so that all the red points are fixed in some position and all
”corners” of the staircase formed by the points in $L_{1}$ lie under $L_{2}$.

Example of an instance in $D^{\prime}$.

It is easy to see that in the setting of the topological lower-bounds due to
Ben-Or [3] the “No” instances fall into at least $n^{n}$ connected components
(characterized by which point on $L_{1}$ dominates each of the points on
$L_{2}$). This implies a $\Omega(n\log n)$ worst case complexity for any
algebraic computation tree solving all instances in $D^{\prime}$. This also
implies that no such computation tree solving this problem on $D^{\prime}$ can
run in $f(n)\not\in\Omega(n\log n)$ time on all “Yes” instances in
$D^{\prime}$. Otherwise we could this algorithm and stop the computation after
$f(n)$ steps to get an algorithm with $O(f(n))$ worst-case complexity. Thus
the claim holds. ∎

One caveat of this proof is that it relies on special instances with linear
degeneracies (three points can be collinear). It is not clear if instance-
optimality is possible when restricted to non-degenerate instances.

## References

  * [1] Peyman Afshani, Jérémy Barbay, and Timothy M. Chan.  Instance-optimal geometric algorithms.  J. ACM, 64(1), March 2017.  doi:10.1145/3046673.
  * [2] Pankaj K. Agarwal and Jirí Matousek.  Relative neighborhood graphs in three dimensions.  Comput. Geom., 2:1–14, 1992.  doi:10.1016/0925-7721(92)90017-M.
  * [3] Michael Ben-Or.  Lower bounds for algebraic computation trees.  In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, page 80–86, New York, NY, USA, 1983. Association for Computing Machinery.  doi:10.1145/800061.808735.
  * [4] Jon Louis Bentley.  Multidimensional binary search trees used for associative searching.  Commun. ACM, 18(9):509–517, September 1975.  doi:10.1145/361002.361007.
  * [5] David Bremner, Erik D. Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried T. Toussaint.  Output-sensitive algorithms for computing nearest-neighbour decision boundaries.  Discret. Comput. Geom., 33(4):593–604, 2005.  doi:10.1007/s00454-004-1152-0.
  * [6] Jean Cardinal, Sébastien Collette, and Stefan Langerman.  Empty region graphs.  Comput. Geom., 42(3):183–195, 2009.  doi:10.1016/j.comgeo.2008.09.003.
  * [7] Timothy M. Chan.  Optimal output-sensitive convex hull algorithms in two and three dimensions.  Discret. Comput. Geom., 16(4):361–368, 1996.  doi:10.1007/BF02712873.
  * [8] Timothy M. Chan.  Output-sensitive results on convex hulls, extreme points, and related problems.  Discret. Comput. Geom., 16(4):369–387, 1996.  doi:10.1007/BF02712874.
  * [9] Xiaomin Chen, János Pach, Mario Szegedy, and Gábor Tardos.  Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.  Random Struct. Algorithms, 34(1):11–23, 2009.  doi:10.1002/rsa.20246.
  * [10] Olivier Devillers, Jeff Erickson, and Xavier Goaoc.  Empty-ellipse graphs.  In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 1249–1257. SIAM, 2008\.  URL: http://dl.acm.org/citation.cfm?id=1347082.1347218.
  * [11] Ralf Hartmut Güting, Otto Nurmi, and Thomas Ottmann.  Fast algorithms for direct enclosures and direct dominances.  J. Algorithms, 10(2):170–186, 1989.  doi:10.1016/0196-6774(89)90011-4.
  * [12] Manabu Ichino and Jack Sklansky.  The relative neighborhood graph for mixed feature variables.  Pattern Recognit., 18(2):161–167, 1985.  doi:10.1016/0031-3203(85)90040-8.
  * [13] J.W. Jaromczyk and G.T. Toussaint.  Relative neighborhood graphs and their relatives.  Proceedings of the IEEE, 80(9):1502–1517, 1992.  doi:10.1109/5.163414.
  * [14] J. Mark Keil and Carl A. Gutwin.  Classes of graphs which approximate the complete euclidean graph.  Discret. Comput. Geom., 7:13–28, 1992.  doi:10.1007/BF02187821.
  * [15] David G. Kirkpatrick and John D. Radke.  A framework for computational morphology.  In Godfried T. TOUSSAINT, editor, Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition, pages 217–248. North-Holland, 1985.  URL: https://www.sciencedirect.com/science/article/pii/B978044487806950013X, doi:https://doi.org/10.1016/B978-0-444-87806-9.50013-X.
  * [16] David G. Kirkpatrick and Raimund Seidel.  The ultimate planar convex hull algorithm?  SIAM J. Comput., 15(1):287–299, 1986.  doi:10.1137/0215021.
  * [17] J. Ian Munro, Mark H. Overmars, and Derick Wood.  Variations on visibility.  In D. Soule, editor, Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, pages 291–299. ACM, 1987.  doi:10.1145/41958.41989.
  * [18] Mark H. Overmars.  Connectability problems.  In Rolf G. Karlsson and Andrzej Lingas, editors, SWAT 88, 1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 5-8, 1988, Proceedings, volume 318 of Lecture Notes in Computer Science, pages 105–112. Springer, 1988.  doi:10.1007/3-540-19487-8\\_11.
  * [19] Mark H. Overmars and Derick Wood.  On rectangular visibility.  J. Algorithms, 9(3):372–390, 1988.  doi:10.1016/0196-6774(88)90028-4.
  * [20] Andrew Chi-Chih Yao.  On constructing minimum spanning trees in k-dimensional spaces and related problems.  SIAM J. Comput., 11(4):721–736, 1982.  doi:10.1137/0211059.