reference model. Figure 19 also highlights that the residuals for most points
are about one order of magnitude lower for the LOST method as compared to the
DLT method.

Figure 18: Point cloud reconstruction of the west facade of Notre-Dame de
Paris. The top row shows the reference model from [113] while the bottom row
is the solution found with the LOST method. Figure 19: Position residuals for
the 3-D reconstruction of Notre-Dame de Pairs using the DLT and LOST methods
as compared to the reference model.

###  7.4 Rendezvous, Proximity Operations, and Docking (RPOD)

Rendezvous, Proximity Operations, and Docking (RPOD) is a critical capability
for a variety of spaceflight applications [114], including human exploration
[115, 116, 117], interplanetary exploration [118], and satellite servicing
[119]. When two spacecraft in nearly circular orbits are close to one another,
their relative dynamics are nearly linear and may be described by the
Clohessy-Wiltshire (CW) equations [63]. It has been known for some time that
the relative state between two particles is unobservable under CW dynamics
when only LOS measurements are available [64, 13]. There are two ways to
reintroduce observability during coasting flight (i.e., with no maneuvers).
The first is to consider the nonlinear dynamics [120]. The second is to alter
the triangulation geometry. This brief example focuses only on the latter of
these these solutions.

Consider the situation where the origin of an LVLH frame is fixed to a chief
spacecraft in a circular orbit. The relative motion of a nearby deputy
spacecraft in this same LVLH frame is governed by the CW equations having a
solution of the form:

$\boldsymbol{\xi}_{i}=\begin{bmatrix}\textbf{\emph{r}}_{i}\\\
\textbf{\emph{v}}_{i}\end{bmatrix}=\begin{bmatrix}\boldsymbol{\Phi}_{\textbf{\emph{r}}\textbf{\emph{r}}}(t_{i},t_{0})&\boldsymbol{\Phi}_{\textbf{\emph{r}}\textbf{\emph{v}}}(t_{i},t_{0})\\\
\boldsymbol{\Phi}_{\textbf{\emph{v}}\textbf{\emph{r}}}(t_{i},t_{0})&\boldsymbol{\Phi}_{\textbf{\emph{v}}\textbf{\emph{v}}}(t_{i},t_{0})\end{bmatrix}\begin{bmatrix}\textbf{\emph{r}}_{0}\\\
\textbf{\emph{v}}_{0}\end{bmatrix}=\boldsymbol{\Phi}(t_{i},t_{0})\boldsymbol{\xi}_{0}$
(126)

where $\textbf{\emph{r}}_{i}$ and $\textbf{\emph{v}}_{i}$ are LVLH position
and velocity of the deputy relative to the chief at time $t_{i}$. The
equations for $\boldsymbol{\Phi}(t_{i},t_{0})$ may be found in Ref. [63] or a
contemporary astrodynamics textbook (e.g., [121]).

Using the notation from Section 6, let $\boldsymbol{\Phi}_{\textbf{\emph{r}}}$
denote the rows of the STM that produce the position vector,

$\boldsymbol{\Phi}_{\textbf{\emph{r}}}(t_{i},t_{0})=\begin{bmatrix}\boldsymbol{\Phi}_{\textbf{\emph{r}}\textbf{\emph{r}}}(t_{i},t_{0})&\boldsymbol{\Phi}_{\textbf{\emph{r}}\textbf{\emph{v}}}(t_{i},t_{0})\end{bmatrix}$
(127)

which is a $3\times 6$ matrix in this case.

Suppose for a moment that LOS measurements are collected between the chief and
deputy spacecraft (the same equations result regardless of the vehicle on
which the camera resides). Since the chief spacecraft is at the origin, this
implies that $\textbf{\emph{p}}_{I_{i}}=0,\;\forall t_{i}$. Hence,
substituting this scenario into Eq. (124), one arrives at

$\begin{bmatrix}\left[\boldsymbol{\ell}_{1}\times\right]\boldsymbol{\Phi}_{\textbf{\emph{r}}}(t_{1},t_{0})\\\
\vdots\\\
\left[\boldsymbol{\ell}_{n}\times\right]\boldsymbol{\Phi}_{\textbf{\emph{r}}}(t_{n},t_{0})\end{bmatrix}\begin{bmatrix}\textbf{\emph{r}}_{0}\\\
\textbf{\emph{v}}_{0}\end{bmatrix}=\textbf{0}_{3n\times 1}$ (128)

Since the result is a homogeneous linear system, it follows that both
$\boldsymbol{\xi}_{0}$ and $\alpha\boldsymbol{\xi}_{0}$ (for $\alpha\neq 0$)
provide equally acceptable solutions to the linear system. There are
infinitely many homothetic solutions $\alpha\boldsymbol{\xi}_{0}$ that
represent an expansion or contraction of the figure (i.e., true deputy’s
trajectory) about the homothetic center (i.e., the chief’s location at the
origin of the LVLH frame). This is nothing more than a triangulation
interpretation of the well-known scale ambiguity associated with angles-only
RelNav that is usually shown by other means (e.g., Ref. [64]).

It is obvious now that scale observability may be introduced by making the
right-hand side of Eq. (128) non-zero. This may be practically achieved by
introducing a known offset in the location of either the camera (on the
deputy) or the observed point (on the chief). Such a situation may occur when
either of the spacecraft are not small when compared to the scale of the
relative motion.

To see this, suppose there is a camera aboard the deputy spacecraft with a
known offset of $\delta\textbf{\emph{r}}_{i}$ at time $t_{i}$. In this case,
the LOS measurement is

$\boldsymbol{\ell}_{i}\propto\textbf{\emph{p}}_{i}-(\textbf{\emph{r}}_{i}+\delta\textbf{\emph{r}}_{i})$
(129)

and so the DLT equation becomes

$\left[\boldsymbol{\ell}_{i}\times\right]\textbf{\emph{r}}_{i}=\left[\boldsymbol{\ell}_{i}\times\right]\left(\textbf{\emph{p}}_{i}-\delta\textbf{\emph{r}}_{i}\right)$
(130)

Therefore, after mapping $\textbf{\emph{r}}_{i}$ to time $t_{0}$,

$\left[\boldsymbol{\ell}_{i}\times\right]\boldsymbol{\Phi}(t_{i},t_{0})\boldsymbol{\xi}_{0}=\left[\boldsymbol{\ell}_{i}\times\right]\left(\textbf{\emph{p}}_{i}-\delta\textbf{\emph{r}}_{i}\right)$
(131)

Letting the localization frame be the LVLH frame (denoted by $L$) and using
the normalization
$\boldsymbol{\ell}_{C_{i}}\propto\textbf{\emph{K}}^{-1}\bar{\textbf{\emph{u}}}_{i}$,

$\left[\textbf{\emph{K}}^{-1}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{L}_{C_{i}}\boldsymbol{\Phi}(t_{i},t_{0})\boldsymbol{\xi}_{0}=\left[\textbf{\emph{K}}^{-1}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{L}_{C_{i}}\left(\textbf{\emph{p}}_{L_{i}}-\delta\textbf{\emph{r}}_{L_{i}}\right)$
(132)

When more than one measurement is available at more than one time, this
expression may be stacked in the usual way to form a linear system

$\begin{bmatrix}\left[\textbf{\emph{K}}^{-1}\bar{\textbf{\emph{u}}}_{1}\times\right]\textbf{\emph{T}}^{L}_{C_{1}}\boldsymbol{\Phi}(t_{1},t_{0})\\\
\vdots\\\
\left[\textbf{\emph{K}}^{-1}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{L}_{C_{i}}\boldsymbol{\Phi}(t_{i},t_{0})\end{bmatrix}\boldsymbol{\xi}_{0}=\begin{bmatrix}\left[\textbf{\emph{K}}^{-1}\bar{\textbf{\emph{u}}}_{1}\times\right]\textbf{\emph{T}}^{L}_{C_{1}}\left(\textbf{\emph{p}}_{L_{1}}-\delta\textbf{\emph{r}}_{L_{1}}\right)\\\
\vdots\\\
\left[\textbf{\emph{K}}^{-1}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{L}_{C_{i}}\left(\textbf{\emph{p}}_{L_{i}}-\delta\textbf{\emph{r}}_{L_{i}}\right)\end{bmatrix}$
(133)

So long as the offsets (and measurement times) are chosen to avoid
$\left[\textbf{\emph{K}}^{-1}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{L}_{C_{i}}\left(\textbf{\emph{p}}_{C_{i}}-\delta\textbf{\emph{r}}_{C_{i}}\right)=0$
for all of the observation times then the problem becomes observable. In most
cases this condition is the same as ensuring
$\textbf{\emph{p}}_{C_{i}}\neq\delta\textbf{\emph{r}}_{C_{i}}$. The idea of
introducing observability by an offset in just the point aboard the deputy
(i.e., $\textbf{\emph{p}}_{C_{i}}=0$ and $\delta\textbf{\emph{r}}_{C_{i}}\neq
0$) was explored in Ref. [122]. The result above demonstrates that an
equivalent solution could be achieved by introducing an offset on the chief
(i.e., $\textbf{\emph{p}}_{C_{i}}\neq 0$ and
$\delta\textbf{\emph{r}}_{C_{i}}=0$).

##  8 Conclusions

Absolute line of sight (LOS) measurements from images may be used to solve
both spacecraft navigation and three-dimensional (3-D) reconstruction problems
via triangulation. The mathematical foundations necessary for triangulation
have been understood since antiquity, and knowledge of this history enhances
the versatility of the modern practitioner. This manuscript reviews the
historical evolution of triangulation algorithms that ultimately led to the
embodiments of the trigonometric solutions that are in widespread use today.
Many variations on these trigonometric solutions [e.g, with the Direct Linear
Transform (DLT), collinearity equations, or Plücker coordinates] are shown to
be equivalent to one another. In the special case of two LOS observations, the
statistically optimal solution of Hartley and Sturm [15] is summarized and the
resulting polynomial of degree six is considered. When the two LOS
observations come from the same camera (e.g., with monocular navigation), the
derivation can be modified to produce a much simpler polynomial of degree two.
Moreover, in the general case of many measurements (from one or many cameras),
it is shown that a Maximum Likelihood Estimate (MLE) may be developed as the
solution to a small linear system (of size $2n\times 3$ for $n$ LOS
measurements)—resulting in the so-called Linear Optimal Sine Triangulation
(LOST) method. The non-iterative LOST method is shown to provide an equivalent
solution to the classical Hartley and Sturm method, but has the comparative
advantages of (1) being scalable to many measurements and (2) not requiring
the solution to a polynomial of degree six. Finally, many of the triangulation
results are also shown to be valid for dynamic systems, especially when the
dynamics are linear. The various algorithms and analytic insights are
validated through a variety of examples, including planetary terrain relative
navigation (TRN), interplanetary optical navigation (OPNAV), 3-D
reconstruction of Notre-Dame de Paris, and angles-only relative navigation
(RelNav).

## Appendix

###  8.1 Analytic Covariance Expressions

####  8.1.1 Direct Linear Transform

The DLT is formulated in Eq. (20) as an ordinary (unweighted) least squares
problem. Given a problem
$\textbf{\emph{H}}\textbf{\emph{x}}=\textbf{\emph{y}}$, recall that the
covariance for a generic weighting is,

$\textbf{\emph{P}}=(\textbf{\emph{H}}^{T}\textbf{\emph{W}}\textbf{\emph{H}})^{-1}(\textbf{\emph{H}}^{T}\textbf{\emph{W}}\textbf{\emph{R}}\textbf{\emph{W}}^{T}\textbf{\emph{H}})(\textbf{\emph{H}}^{T}\textbf{\emph{W}}\textbf{\emph{H}})^{-1}$
(134)

where R is the measurement covariance and W is the measurement weighting
matrix. When $\textbf{\emph{W}}=\textbf{\emph{R}}^{-1}$ the result is the MLE
solution. However, when $\textbf{\emph{W}}=\textbf{\emph{I}}_{n\times n}$, the
result is the ordinary least squares solution having covariance

$\textbf{\emph{P}}=(\textbf{\emph{H}}^{T}\textbf{\emph{H}})^{-1}(\textbf{\emph{H}}^{T}\textbf{\emph{R}}\textbf{\emph{H}})(\textbf{\emph{H}}^{T}\textbf{\emph{H}})^{-1}$
(135)

Substituting into this notation, it follows from Eq. (20), that

$\textbf{\emph{H}}=\begin{bmatrix}\left[\textbf{\emph{K}}_{1}^{-1}\bar{\textbf{\emph{u}}}_{1}\times\right]\textbf{\emph{T}}^{I}_{C_{1}}\\\
\vdots\\\
\left[\textbf{\emph{K}}_{n}^{-1}\bar{\textbf{\emph{u}}}_{n}\times\right]\textbf{\emph{T}}^{I}_{C_{n}}\end{bmatrix}$
(136)

and, therefore,

$\textbf{\emph{H}}^{T}\textbf{\emph{H}}=-\sum_{i=1}^{n}\textbf{\emph{T}}_{I}^{C_{i}}\left[\textbf{\emph{K}}_{i}^{-1}\bar{\textbf{\emph{u}}}_{1}\times\right]^{2}\textbf{\emph{T}}^{I}_{C_{i}}$
(137)

Moreover, obtaining $\textbf{\emph{R}}_{\boldsymbol{\epsilon}_{i}}$ from Eq.
(107) one finds that

$\textbf{\emph{P}}_{DLT}=-(\textbf{\emph{H}}^{T}\textbf{\emph{H}})^{-1}\left(\sum_{i=1}^{n}\textbf{\emph{T}}_{I}^{C_{i}}\left[\textbf{\emph{K}}_{i}^{-1}\bar{\textbf{\emph{u}}}_{i}\times\right]\tilde{\textbf{\emph{R}}}_{\boldsymbol{\epsilon}_{i}}\left[\textbf{\emph{K}}_{i}^{-1}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{I}_{C_{i}}\right)(\textbf{\emph{H}}^{T}\textbf{\emph{H}})^{-1}$
(138)

where everything here is known. The leading negative sign is a result of the
identity $[\,\cdot\,\times]^{T}=-[\,\cdot\,\times]$.

####  8.1.2 Explicit Range

Writing an analytic expression for the covariance of the explicit range method
is difficult in general due to combinatorial nature of the problem. It is not
generally clear which combinations of measurements should be used. Thus, the
discussion that follows focuses only on the two-measurement case. Additional
attention is not warranted since this method is rarely the preferred approach
for triangulation.

To develop the covariance, begin with the expression from Eq. (50)

$\textbf{\emph{r}}_{I}=\frac{1}{n}\sum_{i=1}^{n}\textbf{\emph{p}}_{I_{i}}-\rho_{i}\textbf{\emph{a}}_{I_{i}}$
(139)

and then compute the differential

$\delta\textbf{\emph{r}}_{I}=-\frac{1}{n}\sum_{i=1}^{n}\delta\rho_{i}\textbf{\emph{a}}_{I_{i}}+\rho_{i}\delta\textbf{\emph{a}}_{I_{i}}$
(140)

For the case of $n=2$, this may be written as

$-2\delta\textbf{\emph{r}}=\textbf{\emph{A}}_{12}\begin{bmatrix}\delta\rho_{1}\\\
\delta\rho_{2}\end{bmatrix}+\textbf{\emph{B}}_{12}\begin{bmatrix}\delta\textbf{\emph{a}}_{I_{1}}\\\
\delta\textbf{\emph{a}}_{I_{2}}\end{bmatrix}$ (141)
$\textbf{\emph{A}}_{12}=\begin{bmatrix}\textbf{\emph{a}}_{I_{1}}&\textbf{\emph{a}}_{I_{2}}\end{bmatrix}\quad\text{and}\quad\textbf{\emph{B}}_{12}=\begin{bmatrix}\rho_{1}\textbf{\emph{I}}_{3\times
3}&\rho_{2}\textbf{\emph{I}}_{3\times 3}\end{bmatrix}$ (142)

Similarly, taking the differential of Eq. (49) for $n=2$, one obtains

$\begin{bmatrix}-1&\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}}\\\
-\textbf{\emph{a}}^{T}_{I_{2}}\textbf{\emph{a}}_{I_{1}}&1\end{bmatrix}\begin{bmatrix}\delta\rho_{1}\\\
\delta\rho_{2}\end{bmatrix}=\begin{bmatrix}\textbf{\emph{d}}^{T}_{I_{12}}\delta\textbf{\emph{a}}_{I_{1}}-\rho_{2}(\textbf{\emph{a}}^{T}_{I_{2}}\delta\textbf{\emph{a}}_{I_{1}}+\textbf{\emph{a}}^{T}_{I_{1}}\delta\textbf{\emph{a}}_{I_{2}})\\\
\textbf{\emph{d}}_{I_{12}}\delta\textbf{\emph{a}}_{I_{2}}+\rho_{1}(\textbf{\emph{a}}^{T}_{I_{2}}\delta\textbf{\emph{a}}_{I_{1}}+\textbf{\emph{a}}^{T}_{I_{1}}\delta\textbf{\emph{a}}_{I_{2}})\end{bmatrix}$
(143)

which may be rewritten as

$\begin{bmatrix}\delta\rho_{1}\\\
\delta\rho_{2}\end{bmatrix}=\textbf{\emph{C}}_{12}\begin{bmatrix}\delta\textbf{\emph{a}}_{I_{1}}\\\
\delta\textbf{\emph{a}}_{I_{2}}\end{bmatrix}$ (144)
$\textbf{\emph{C}}_{12}=\frac{1}{(\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1}\begin{bmatrix}1&-\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}}\\\
\textbf{\emph{a}}^{T}_{I_{2}}\textbf{\emph{a}}_{I_{1}}&-1\end{bmatrix}\begin{bmatrix}\textbf{\emph{d}}^{T}_{I_{12}}-\rho_{2}\textbf{\emph{a}}^{T}_{I_{2}}&-\rho_{2}\textbf{\emph{a}}^{T}_{I_{1}}\\\
\rho_{1}\textbf{\emph{a}}^{T}_{C_{2}}&\textbf{\emph{d}}_{I_{12}}+\rho_{1}\textbf{\emph{a}}_{I_{1}}\end{bmatrix}$
(145)

Substituting Eq. (144) into Eq. (141), it follows that

$\delta\textbf{\emph{r}}=-\frac{1}{2}(\textbf{\emph{A}}_{12}\textbf{\emph{C}}_{12}+\textbf{\emph{B}}_{12})\begin{bmatrix}\delta\textbf{\emph{a}}_{C_{1}}\\\
\delta\textbf{\emph{a}}_{C_{2}}\end{bmatrix}$ (146)

Also, computing
$\partial\textbf{\emph{a}}_{C_{i}}/\partial\bar{\textbf{\emph{x}}}_{i}$,
observe that

$\begin{bmatrix}\delta\textbf{\emph{a}}_{C_{1}}\\\
\delta\textbf{\emph{a}}_{C_{2}}\end{bmatrix}=-\textbf{\emph{D}}_{12}\begin{bmatrix}\delta\bar{\textbf{\emph{x}}}_{1}\\\
\delta\bar{\textbf{\emph{x}}}_{2}\end{bmatrix}$ (147)
$\textbf{\emph{D}}_{12}=\begin{bmatrix}\|\bar{\textbf{\emph{x}}}^{T}_{1}\|^{-1}\textbf{\emph{T}}^{C_{1}}_{I}\left[\textbf{\emph{a}}_{C_{1}}\times\right]^{2}&\textbf{0}_{3\times
3}\\\ \textbf{0}_{3\times
3}&\|\bar{\textbf{\emph{x}}}^{T}_{2}\|^{-1}\textbf{\emph{T}}^{C_{2}}_{I}\left[\textbf{\emph{a}}_{C_{2}}\times\right]^{2}\end{bmatrix}$
(148)

Which, after substitution of Eq. (147) into Eq. (146), yields

$\delta\textbf{\emph{r}}=\frac{1}{2}(\textbf{\emph{A}}_{12}\textbf{\emph{C}}_{12}+\textbf{\emph{B}}_{12})\textbf{\emph{D}}_{12}\begin{bmatrix}\delta\bar{\textbf{\emph{x}}}_{1}\\\
\delta\bar{\textbf{\emph{x}}}_{2}\end{bmatrix}$ (149)

And, finally,

$\textbf{\emph{P}}_{RNG}=E[\delta\textbf{\emph{r}}\,\delta\textbf{\emph{r}}^{T}]=\frac{1}{4}(\textbf{\emph{A}}_{12}\textbf{\emph{C}}_{12}+\textbf{\emph{B}}_{12})\textbf{\emph{D}}_{12}\textbf{\emph{R}}_{\bar{\textbf{\emph{x}}}}\textbf{\emph{D}}^{T}_{12}(\textbf{\emph{A}}_{12}\textbf{\emph{C}}_{12}+\textbf{\emph{B}}_{12})^{T}$
(150)

####  8.1.3 Hartley and Sturm Polynomial

To develop the analytic covariance for the Hartley and Sturm method, begin
with the measurement model from Eq. (57)

$\textbf{\emph{u}}_{i}=\frac{\textbf{\emph{S}}\textbf{\emph{K}}_{i}\textbf{\emph{T}}^{I}_{C_{i}}(\textbf{\emph{p}}_{I_{i}}-\textbf{\emph{r}}_{I})}{\textbf{\emph{k}}^{T}\textbf{\emph{K}}_{i}\textbf{\emph{T}}^{I}_{C_{i}}(\textbf{\emph{p}}_{I_{i}}-\textbf{\emph{r}}_{I})}$
(151)

Since this method (as modified here) explicitly minimizes the covariance-
weighted reprojection error, one obtains a covariance

$\textbf{\emph{P}}_{\textbf{\emph{r}}}=\left[\sum_{i=1}^{2}\textbf{\emph{A}}^{T}_{i}\textbf{\emph{R}}^{-1}_{\textbf{\emph{u}}_{i}}\textbf{\emph{A}}_{i}\right]^{-1}$
(152)

where

$\textbf{\emph{A}}_{i}=\frac{\partial\textbf{\emph{u}}_{i}}{\partial\textbf{\emph{r}}_{I}}=\frac{-\textbf{\emph{S}}\textbf{\emph{K}}_{i}\textbf{\emph{T}}^{I}_{C_{i}}}{\textbf{\emph{k}}^{T}\textbf{\emph{K}}_{i}\textbf{\emph{T}}^{I}_{C_{i}}(\textbf{\emph{p}}_{I_{i}}-\textbf{\emph{r}}_{I})}\left(\textbf{\emph{I}}_{3\times
3}-\frac{(\textbf{\emph{p}}_{I_{i}}-\textbf{\emph{r}}_{I})\textbf{\emph{k}}^{T}\textbf{\emph{K}}_{i}\textbf{\emph{T}}^{I}_{C_{i}}}{\textbf{\emph{k}}^{T}\textbf{\emph{K}}_{i}\textbf{\emph{T}}^{I}_{C_{i}}(\textbf{\emph{p}}_{I_{i}}-\textbf{\emph{r}}_{I})}\right)$
(153)

This may be simplified somewhat by considering the structure of
$\textbf{\emph{A}}_{i}$ and $\textbf{\emph{R}}_{\textbf{\emph{u}}_{i}}$.
First, recognize that
$\textbf{\emph{k}}^{T}\textbf{\emph{K}}_{i}=\textbf{\emph{k}}^{T}$. Also,
making use of the identity
$(\textbf{\emph{a}}^{T}\textbf{\emph{b}})\textbf{\emph{I}}_{3\times
3}-\textbf{\emph{b}}\textbf{\emph{a}}^{T}=[\textbf{\emph{a}}\times][\textbf{\emph{b}}\times]$,
one observes that $\textbf{\emph{A}}_{i}$ becomes

$\textbf{\emph{A}}_{i}=\frac{1}{\gamma^{2}_{i}}\textbf{\emph{S}}\textbf{\emph{K}}_{i}\textbf{\emph{T}}^{I}_{C_{i}}\left[\textbf{\emph{T}}^{C_{i}}_{I}\textbf{\emph{k}}\times\right]\left[(\textbf{\emph{p}}_{I_{i}}-\textbf{\emph{r}}_{I})\times\right]$
(154)

where $\gamma_{i}$ is from Eq. (108) and may also be written as
$\gamma_{i}=\textbf{\emph{k}}^{T}\textbf{\emph{T}}^{I}_{C_{i}}(\textbf{\emph{p}}_{I_{i}}-\textbf{\emph{r}}_{I})$.
Further, recognizing that
$\bar{\textbf{\emph{x}}}_{i}=\textbf{\emph{T}}^{I}_{C_{i}}(\textbf{\emph{p}}_{I_{i}}-\textbf{\emph{r}}_{I})/\gamma_{i}$,

$\textbf{\emph{A}}_{i}=\frac{1}{\gamma_{i}}\textbf{\emph{S}}\textbf{\emph{K}}_{i}\textbf{\emph{T}}^{I}_{C_{i}}\left[\textbf{\emph{T}}^{C_{i}}_{I}\textbf{\emph{k}}\times\right]\left[\textbf{\emph{T}}^{C_{i}}_{i}\bar{\textbf{\emph{x}}}_{i}\times\right]$
(155)

Factoring out the rotation $\textbf{\emph{T}}^{I}_{C_{i}}$

$\textbf{\emph{A}}_{i}=\frac{1}{\gamma_{i}}\textbf{\emph{S}}\textbf{\emph{K}}_{i}\left[\textbf{\emph{k}}\times\right]\left[\bar{\textbf{\emph{x}}}_{i}\times\right]\textbf{\emph{T}}^{I}_{C_{i}}$
(156)

If
$\textbf{\emph{R}}^{-1}_{\textbf{\emph{u}}_{i}}=\sigma^{-2}_{\textbf{\emph{u}}_{i}}\textbf{\emph{I}}_{2\times
2}$, substituting into

$\textbf{\emph{P}}^{-1}_{\textbf{\emph{r}}}=\sum_{i=1}^{n}\frac{1}{\sigma^{2}_{\textbf{\emph{x}}_{i}}\gamma^{2}_{i}}\textbf{\emph{T}}^{C_{i}}_{I}\left[\bar{\textbf{\emph{x}}}_{i}\times\right]\left[\textbf{\emph{k}}\times\right]\textbf{\emph{K}}^{T}_{i}\textbf{\emph{S}}^{T}\textbf{\emph{S}}\textbf{\emph{K}}_{i}\left[\textbf{\emph{k}}\times\right]\left[\bar{\textbf{\emph{x}}}_{i}\times\right]\textbf{\emph{T}}^{I}_{C_{i}}$
(157)

Suppose that pixels are square ($d_{x}=d_{y}$) and that there is no detector
skewness ($\alpha=0$) when forming the camera calibration matrix
$\textbf{\emph{K}}_{i}$. Under this condition, note that
$\left[\textbf{\emph{k}}\times\right]\textbf{\emph{K}}_{i}^{T}\textbf{\emph{S}}^{T}\textbf{\emph{S}}\textbf{\emph{K}}_{i}\left[\textbf{\emph{k}}\times\right]=-d^{2}_{x_{i}}\textbf{\emph{S}}^{T}\textbf{\emph{S}}$.
Moreover, since
$\bar{\textbf{\emph{x}}}_{i}=\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}$,

$\textbf{\emph{P}}^{-1}_{\textbf{\emph{r}}}=-\sum_{i=1}^{n}\frac{d^{2}_{x_{i}}}{\sigma^{2}_{\textbf{\emph{u}}_{i}}\gamma^{2}_{i}}\textbf{\emph{T}}^{C_{i}}_{I}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{S}}^{T}\textbf{\emph{S}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{I}_{C_{i}}$
(158)

Recognizing that
$\sigma_{\textbf{\emph{x}}_{i}}=\sigma_{\textbf{\emph{u}}_{i}}/d_{x}$, this
becomes

$\textbf{\emph{P}}^{-1}_{\textbf{\emph{r}}}=-\sum_{i=1}^{n}\frac{1}{\sigma^{2}_{\textbf{\emph{x}}_{i}}\gamma^{2}_{i}}\textbf{\emph{T}}^{C_{i}}_{I}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{S}}^{T}\textbf{\emph{S}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{I}_{C_{i}}$
(159)

which is identical to Eq. (164). Hence, the analytic covariance for the HS and
LOST methods is the same when
$\textbf{\emph{R}}_{\textbf{\emph{u}}_{i}}=\sigma^{2}_{\textbf{\emph{u}}_{i}}\textbf{\emph{I}}_{2\times
2}=d_{x_{i}}^{2}\sigma_{\textbf{\emph{x}}_{i}}^{2}\textbf{\emph{I}}_{2\times
2}=d_{x_{i}}^{2}\textbf{\emph{R}}_{\textbf{\emph{x}}_{i}}$.

####  8.1.4 LOST

The analytic LOST covariance is given from Eq. (116), repeated here as

$\textbf{\emph{P}}_{\textbf{\emph{r}}}=-\left(\sum_{i=1}^{n}\textbf{\emph{T}}_{I}^{C_{i}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}\times\right]\textbf{\emph{R}}^{\dagger}_{\boldsymbol{\epsilon}_{i}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}\times\right]\textbf{\emph{T}}^{I}_{C_{i}}\right)^{-1}$
(160)

The complicating term for analytic analysis is
$\textbf{\emph{R}}^{\dagger}_{\boldsymbol{\epsilon}_{i}}$. This is addressed
first. Beginning with the definition of
$\textbf{\emph{R}}_{\boldsymbol{\epsilon}_{i}}$ from Eq. (107), which is
written compactly as

$\textbf{\emph{R}}_{\boldsymbol{\epsilon}_{i}}=-\gamma^{2}_{i}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{R}}_{\bar{\textbf{\emph{x}}}_{i}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]$
(161)

where $\gamma_{i}$ is from Eq. (108). Under the case when
$\textbf{\emph{R}}_{\bar{\textbf{\emph{x}}}}=\sigma^{2}_{\bar{\textbf{\emph{x}}}_{i}}\textbf{\emph{S}}^{T}\textbf{\emph{S}}$,
observe that

$\textbf{\emph{R}}^{\dagger}_{\boldsymbol{\epsilon}_{i}}=\frac{1}{\sigma^{2}_{\bar{\textbf{\emph{x}}}_{i}}\gamma^{2}_{i}\|\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\|^{4}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]^{2}\textbf{\emph{S}}^{T}\textbf{\emph{S}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]^{2}$
(162)

Substituting this into the Eq. (160) leads to

$\textbf{\emph{P}}^{-1}_{\textbf{\emph{r}}}=-\sum_{i=1}^{n}\frac{1}{\sigma^{2}_{\bar{\textbf{\emph{x}}}_{i}}\gamma^{2}_{i}\|\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\|^{4}}\textbf{\emph{T}}_{I}^{C_{i}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]^{3}\textbf{\emph{S}}^{T}\textbf{\emph{S}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]^{3}\textbf{\emph{T}}^{I}_{C_{i}}$
(163)

which simplifies to

$\textbf{\emph{P}}^{-1}_{\textbf{\emph{r}}}=-\sum_{i=1}^{n}\frac{1}{\sigma^{2}_{\bar{\textbf{\emph{x}}}_{i}}\gamma^{2}_{i}}\textbf{\emph{T}}_{I}^{C_{i}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{S}}^{T}\textbf{\emph{S}}\left[\textbf{\emph{K}}^{-1}_{i}\bar{\textbf{\emph{u}}}_{i}\times\right]\textbf{\emph{T}}^{I}_{C_{i}}$
(164)

###  8.2 Equivalence of the Trigonometric Solutions

When there are two LOS measurements ($n=2$) the DLT and explicit range methods
are equivalent. To begin, one can analytically find the position estimate by
the explicit range as

$\textbf{\emph{r}}_{I}=\frac{1}{2}\sum^{2}_{i=1}(\textbf{\emph{p}}_{i}-\rho_{i}\textbf{\emph{a}}_{i})$
(165)
$\textbf{\emph{r}}_{I}=\frac{1}{2}(\textbf{\emph{p}}_{1}+\textbf{\emph{p}}_{2})-\frac{1}{2}\begin{bmatrix}\textbf{\emph{a}}_{I_{1}}&\textbf{\emph{a}}_{I_{2}}\end{bmatrix}\begin{bmatrix}\rho_{1}\\\
\rho_{2}\end{bmatrix}$ (166) $\displaystyle\hat{\textbf{\emph{r}}}_{I}$
$\displaystyle=\frac{1}{2}(\textbf{\emph{p}}_{1}+\textbf{\emph{p}}_{2})-\frac{1}{2}\begin{bmatrix}\textbf{\emph{a}}_{I_{1}}&\textbf{\emph{a}}_{I_{2}}\end{bmatrix}\left(\frac{1}{(\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1}\begin{bmatrix}1&-\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}}\\\
\textbf{\emph{a}}^{T}_{I_{2}}\textbf{\emph{a}}_{I_{1}}&-1\end{bmatrix}\begin{bmatrix}\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{d}}_{I_{12}}\\\
\textbf{\emph{a}}^{T}_{{}_{I}2}\textbf{\emph{d}}_{I_{12}}\end{bmatrix}\right)$
(167)
$\displaystyle=\frac{\left((\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1\right)(\textbf{\emph{p}}_{1}+\textbf{\emph{p}}_{2})+\textbf{\emph{a}}_{I_{1}}\left(\textbf{\emph{a}}_{I_{1}}^{T}\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}_{I_{2}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})-\textbf{\emph{a}}_{I_{1}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})\right)+\textbf{\emph{a}}_{I_{2}}\left(\textbf{\emph{a}}_{I_{2}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})-\textbf{\emph{a}}_{I_{2}}^{T}\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}_{I_{1}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})\right)}{2\left((\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1\right)}$
$\displaystyle=\frac{\left((\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1\right)(\textbf{\emph{p}}_{1}+\textbf{\emph{p}}_{2})-\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}_{I_{1}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})+\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}_{I_{2}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})+\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}_{I_{1}}^{T}\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}_{I_{2}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})-\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}_{I_{2}}^{T}\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}_{I_{1}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})}{2\left((\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1\right)}$

Now, consider the two-LOS version of the DLT from Eq. (18). Choose to describe
the LOS measurement by
$\boldsymbol{\ell}_{i}=\alpha_{i}\textbf{\emph{a}}_{i}$, where $\alpha_{i}\neq
0$ is the scaling associated with the unit vector LOS $\textbf{\emph{a}}_{i}$,
such that

$\begin{bmatrix}\alpha_{1}\left[\textbf{\emph{a}}_{1}\times\right]\\\
\alpha_{2}\left[\textbf{\emph{a}}_{2}\times\right]\end{bmatrix}\textbf{\emph{r}}=\begin{bmatrix}\alpha_{1}\left[\textbf{\emph{a}}_{1}\times\right]\textbf{\emph{p}}_{1}\\\
\alpha_{2}\left[\textbf{\emph{a}}_{2}\times\right]\textbf{\emph{p}}_{2}\end{bmatrix}$
(168)

Solving this linear system in the least squares sense for r yields

$\hat{\textbf{\emph{r}}}=\left(\sum_{i=1}^{2}\alpha_{i}^{2}\left[\textbf{\emph{a}}_{i}\times\right]^{2}\right)^{-1}\sum_{i=1}^{2}\alpha_{i}^{2}\left[\textbf{\emph{a}}_{i}\times\right]^{2}\textbf{\emph{p}}_{i}$
(169)

Recalling that that if a is a $3\times 1$ unit vector then
$-\left[\textbf{\emph{a}}\times\right]^{2}=\textbf{\emph{I}}_{3\times
3}-\textbf{\emph{a}}\textbf{\emph{a}}^{T}$, then one may write

$\displaystyle\frac{\left(\sum_{i=1}^{2}\alpha_{i}^{2}\left[\textbf{\emph{a}}_{i}\times\right]^{2}\right)}{-(\alpha_{1}^{2}+\alpha_{2}^{2})}$
$\displaystyle=\textbf{\emph{I}}_{3\times
3}\underbrace{-\frac{\alpha_{1}^{2}}{\alpha_{1}^{2}+\alpha_{2}^{2}}}_{\beta_{1}}\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{1}}\underbrace{-\frac{\alpha_{2}^{2}}{\alpha_{1}^{2}+\alpha_{2}^{2}}}_{\beta_{2}}\textbf{\emph{a}}^{T}_{I_{2}}\textbf{\emph{a}}_{I_{2}}$
(170)

The matrices $\textbf{\emph{a}}^{T}_{i}\textbf{\emph{a}}_{i}$ are both rank
one, and it is possible to analytically invert this sum of matrices with the
Sherman-Morrison formula (applied twice). It is also useful to consider that
$1+\beta_{1}=-\beta_{2}$, so that the inverse finally becomes

$\displaystyle\left(\frac{\left(\sum_{i=1}^{2}\alpha_{i}^{2}\left[\textbf{\emph{a}}_{i}\times\right]^{2}\right)}{-(\alpha_{1}^{2}+\alpha_{2}^{2})}\right)^{-1}$
$\displaystyle=\textbf{\emph{I}}_{3\times
3}-\beta_{1}\frac{\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}^{T}_{I_{1}}}{1+\beta_{1}}-\frac{\beta_{2}\left(\textbf{\emph{I}}_{3\times
3}-\beta_{1}\frac{\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}^{T}_{I_{1}}}{1+\beta_{1}}\right)\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}^{T}_{I_{2}}\left(\textbf{\emph{I}}_{3\times
3}-\beta_{1}\frac{\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}^{T}_{I_{1}}}{1+\beta_{1}}\right)}{1+\beta_{2}\textbf{\emph{a}}^{T}_{I_{2}}\left(\textbf{\emph{I}}_{3\times
3}-\beta_{1}\frac{\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}^{T}_{I_{1}}}{1+\beta_{1}}\right)\textbf{\emph{a}}_{I_{2}}}$
(171)

When the two measurements are equally weighted (i.e., when
$\alpha_{1}=\alpha_{2}$), one finds that $\beta_{1}=\beta_{2}=-1/2$, so the
expression in Eq. (171) becomes

$\left(\frac{\left(\sum_{i=1}^{2}\alpha_{i}^{2}\left[\textbf{\emph{a}}_{i}\times\right]^{2}\right)}{-(\alpha_{1}^{2}+\alpha_{2}^{2})}\right)^{-1}=-\frac{-\left((\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1\right)(\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}^{T}_{I_{1}}+\textbf{\emph{I}}_{3\times
3})+(\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}^{T}_{I_{1}}+\textbf{\emph{I}}_{3\times
3})\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}^{T}_{I_{2}}(\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}^{T}_{I_{1}}+\textbf{\emph{I}}_{3\times
3})}{(\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1}$ (172)

Expanding Eq. (169), the position given by the DLT is therefore

$\hat{\textbf{\emph{r}}}=\frac{1}{-(\alpha_{1}^{2}+\alpha_{2}^{2})}\left(\frac{\left(\sum_{i=1}^{2}\alpha_{i}^{2}\left[\textbf{\emph{a}}_{i}\times\right]^{2}\right)}{-(\alpha_{1}^{2}+\alpha_{2}^{2})}\right)^{-1}\left(\alpha_{1}^{2}\left[\textbf{\emph{a}}_{I_{1}}\times\right]^{2}\textbf{\emph{p}}_{1}+\alpha_{2}^{2}\left[\textbf{\emph{a}}_{I_{2}}\times\right]^{2}\textbf{\emph{p}}_{2}\right)$
(173)

which, under the assumption of $\alpha_{1}=\alpha_{2}$ (i.e.,
$\beta_{1}=\beta_{2}=-1/2$) and after substitution from Eq. (172), becomes

$\hat{\textbf{\emph{r}}}=\frac{\left((\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1\right)(\textbf{\emph{p}}_{2}+\textbf{\emph{p}}_{1})-\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}_{I_{1}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})+\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}_{I_{2}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})+\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}_{I_{1}}^{T}\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}_{I_{2}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})-\textbf{\emph{a}}_{I_{2}}\textbf{\emph{a}}_{I_{2}}^{T}\textbf{\emph{a}}_{I_{1}}\textbf{\emph{a}}_{I_{1}}^{T}(\textbf{\emph{p}}_{2}-\textbf{\emph{p}}_{1})}{2\left((\textbf{\emph{a}}^{T}_{I_{1}}\textbf{\emph{a}}_{I_{2}})^{2}-1\right)}$
(174)

Thus, the equally-weighted unit vector DLT [Eq. (174)] and the explicit range
[Eq. (167)] give the same position for two LOS observations.

## Acknowledgments

The authors thank Peter Sturm for insightful conversations about triangulation
and his feedback on this manuscript.

## References

  * Christian et al. [2019] Christian, J. A., McMahon, J., DellaGuistina, D. N., Ernst, C. M., Russell, R. P., Golish, D. R., McCabe, J. S., S, K., Lauretta, D. S., Gay, P., and Schoch, P., “Resolved Imagery as a Tool for Space Science and Exploration,” _NASA Exploration Science Forum_ , 2019.
  * Gaskell et al. [2008] Gaskell, R. W., Barnouin-Jha, O. S., Scheers, D. J., and et al., “Characterizing and Navigating Small Bodies with Imaging Data,” _Meteoritics & Planetary Science_, Vol. 43, No. 6, 2008, pp. 1049–1061.  10.1111/j.1945-5100.2008.tb00692.x.
  * Palmer and et al. [2022] Palmer, E. E., and et al., “Practical Stereophotoclinometry for Modeling Shape and Topography on Planetary Missions,” _The Planetary Science Journal_ , Vol. 3, 2022.  10.3847/PSJ/ac460f.
  * Owen et al. [2008] Owen, W., Duxbury, T., Acton, C., Synnott, S., Riedel, J., and Bhaskaran, S., “A Brief History of Optical Navigation at JPL,” _AAS Guidance and Control Conference_ , 2008.
  * Christian [2021] Christian, J. A., “A Tutorial on Horizon-Based Optical Navigation and Attitude Determination with Space Imaging Systems,” _IEEE Access_ , 2021, pp. 19,819–19,853.  10.1109/ACCESS.2021.3051914.
  * Driedger and Ferguson [2021] Driedger, M., and Ferguson, P., “Feasibility Study of an Orbital Navigation Filter Using Resident Space Object Observations,” _Journal of Guidance, Control, and Dynamics_ , Vol. 44, No. 3, 2021, pp. 622–628.  10.2514/1.G005210.
  * Bradley et al. [2020] Bradley, N., Olikara, Z., Bhsakaran, S., and Young, B., “Cislunar Navigation Accuracy Using Optical Observations of Natural and Artificial Targets,” _Journal of Spacecraft and Rockets_ , Vol. 57, No. 4, 2020, pp. 777–792.  10.2514/1.A34694.
  * Karimi and Mortari [2015] Karimi, R. R., and Mortari, D., “Interplanetary Autonomous Navigation Using Visible Planets,” _Journal of Guidance, Control, and Dynamics_ , Vol. 38, No. 6, 2015, pp. 1151–1156.  10.2514/1.G000575.
  * Broschart et al. [2019] Broschart, S. B., Bradley, N., and Bhsakaran, S., “Kinematic Approximation of Position Accuracy Achieved Using Optical Observations of Distant Asteroids,” _Journal of Spacecraft and Rockets_ , Vol. 56, No. 5, 2019, pp. 1383–1392.  10.2514/1.A34354.
  * Hinga [2020] Hinga, M. B., “Cis-Lunar Autonomous Navigation via Implementation of Optical Asteroid Angle-Only Measurements,” _21st Advanced Maui Optical and Space Surveillance Technologies (AMOS) Conference_ , Maui, HI, 2020.
  * Franzese and Topputo [2022] Franzese, V., and Topputo, F., “Deep-Space Optical Navigation Exploiting Multiple Beacons,” _The Journal of the Astronautical Sciences_ , 2022.  10.1007/s40295-022-00303-5.
  * Cheng et al. [2003] Cheng, Y., Johnson, A., Matthies, L., and Olson, C., “Optical Landmark Detection for Spacecraft Navigation,” _AAS/AIAA Astrodynamics Specialist Conference_ , 2003.
  * Woffinden and Geller [2009] Woffinden, D. C., and Geller, D. K., “Observability Criteria for Angles-Only Navigation,” _IEEE Transactions on Aerospace and Electronic Systems_ , Vol. 45, No. 3, 2009, pp. 1194–1208.  10.1109/TAES.2009.5259193.
  * McKee et al. [2022] McKee, P., Kowalski, J., and Christian, J. A., “Navigation and star identification for an interstellar mission,” _Acta Astronautica_ , Vol. 192, 2022, pp. 390–401.  10.1016/j.actaastro.2021.12.007.
  * Hartley and Sturm [1997] Hartley, R. I., and Sturm, P., “Triangulation,” _Computer Vision and Image Understanding_ , Vol. 68, No. 2, 1997, pp. 146–157.  10.1006/cviu.1997.0547.
  * Stewénius et al. [2005] Stewénius, H., Schaffalitzky, F., and Nistér, D., “How Hard is 3-View Triangulation Really?” _IEEE International Conference on Computer Vision (ICCV’05)_ , 2005.  10.1109/ICCV.2005.115.
  * Chace and Manning [1927] Chace, A. B., and Manning, H. P., _The Rhind Mathematical Papyrus, British Museum 10057 and 10058, Vol. 1: Free Translation and Commentary_ , Mathematical Association of America, Oberlin, OH, 1927, pp. 96–99.  URL https://hdl.handle.net/2027/mdp.39015017389894.
  * Molinsky [2015] Molinsky, M., “Some Original Sources for Modern Tales of Thales — The Tale of the Pyramids,” _Convergence_ , 2015.
  * Euclid et al. [1570] Euclid, Billingsley, H., Dee, J., Candale, F. D. F., and Day, J., _The elements of geometrie of the most auncient philosopher Evclide of Megara_ , Imprinted at London: By Iohn Daye, 1570.  URL https://www.loc.gov/item/03020856/.
  * Archibald [1950] Archibald, R. C., “The First Translation of Euclid’s Elements into English and its Source,” _The American Mathematical Monthly_ , Vol. 57, No. 7P1, 1950, pp. 443–452.  10.1080/00029890.1950.11990256.
  * Toomer [1974a] Toomer, G. J., “The Chord Table of Hipparchus and the Early History of Greek Trigonometry,” _Centarus_ , Vol. 18, No. 1, 1974a, pp. 6–28.  10.1111/j.1600-0498.1974.tb00205.x.
  * Ptolemy active 2nd century and Toomer [1984] Ptolemy active 2nd century, and Toomer, G. J., _Ptolemy’s Almagest, translated and annotated by G.J. Toomer_ , Springer-Verlag, New-York, 1984.
  * Toomer [1974b] Toomer, G. J., “Hipparchus on the Distances of the Sun and Moon,” _Archive for History of Exact Sciences_ , Vol. 14, No. 2, 1974b, pp. 126–142.
  * Lorch [2002] Lorch, R., “Greek-Arabic-Latin: The Transmission of Mathematical Texts in the Middle Ages,” _Science in Context_ , Vol. 14, No. 1–2, 2002, pp. 313–331.  10.1017/S0269889701000114.
  * Frisius [1533] Frisius, G., _Libellus de locorum describendorum ratione_ , 1533.
  * Pogo [1935] Pogo, A., “Gemma Frisius, His Method of Determining Differences of Longitude by Transporting Timepieces (1530), and His Treatise on Triangulation (1533),” _Isis_ , Vol. 22, No. 2, 1935, pp. 469–506.
  * Haasbroek [1968] Haasbroek, N. D., _Gemma Frisius, Tycho Brahe and Snellius and Their Triangulations_ , Rijkscommissie voor Geodesie, Delft, Netherlands, 1968.
  * Snellius [1617] Snellius, W., _De Terrae ambitus vera quantitate_ , 1617.  URL https://mdz-nbn-resolving.de/details:bsb10806698.
  * Breitenberger [1984] Breitenberger, E., “Gauss’s geodesy and the axiom of parallels,” _Archive for History of Exact Sciences_ , Vol. 31, No. 3, 1984, pp. 273–289.  10.1007/BF00327704.
  * Gauss [1828] Gauss, C. F., _Supplementum theoriae combinationis observationum erroribus minimis obnoxiae_ , typis Dieterichianis, Göttingen, 1828.  10.3931/e-rara-2858.
  * McCaw [1918] McCaw, G. T., “Resection in Survey,” _The Geographical Journal_ , Vol. 52, No. 2, 1918, pp. 105–123.  10.2307/1779558.
  * Bernard et al. [2018] Bernard, A. J., Nafi, A. M., and Geller, D. K., “Using Triangulation in Optical Orbit Determination,” _AAS/AIAA Astrodynamics Specialist Conference_ , 2018.
  * Chen et al. [2021] Chen, L., Liu, C., Li, Z., and Kang, Z., “A New Triangulation Algorithm for Positioning Space Debris,” _Remote Sensing_ , Vol. 13, No. 23, 2021.  10.3390/rs13234878.
  * Pollefeys et al. [2000] Pollefeys, M., Koch, R., Vergauwen, M., and Van Gool, L., “Automated reconstruction of 3D scenes from sequences of images,” _ISPRS Journal of Photogrammetry and Remote Sensing_ , Vol. 55, No. 4, 2000, pp. 251–267.  10.1016/S0924-2716(00)00023-X.
  * Snavely et al. [2008] Snavely, N., Seitz, S. M., and Szeliski, R., “Modeling the World from Internet Photo Collections,” _International Journal of Computer Vision_ , Vol. 80, 2008, pp. 189–210.  10.1007/s11263-007-0107-3.
  * Poirot and McWilliams [1976] Poirot, J. L., and McWilliams, G. V., “Navigation by Back Triangulation,” _IEEE Transactions on Aerospace and Electronic Systems_ , Vol. 12, No. 2, 1976, pp. 270–274.
  * Feissel and Mignard [1998] Feissel, M., and Mignard, F., “The adoption of ICRS on 1 January 1998: meaning and consequences,” _Astronomy and Astrophysics_ , Vol. 331, 1998, pp. L33–L36.
  * Ma et al. [1998] Ma, C., Arias, E., Eubanks, T., Fey, A., Gontier, A., Jacobs, C., Sovers, O., Archinal, B., and Charlot, P., “The International Celestial Reference Frame as Realized by Very Long Baseline Interferometry,” _The Astronomical Journal_ , Vol. 116, 1998, pp. 516–546.  10.1086/300408.
  * Fey et al. [2015] Fey, A., Gordon, D., and et al., “The Second International Celestial Reference Frame by Very Long Baseline Interferometry,” _The Astronomical Journal_ , Vol. 150, 2015.  10.1088/0004-6256/150/2/58.
  * Kaplan [2011] Kaplan, G. H., “Angles-Only Navigation: Position and Velocity Solution from Absolute Triangulation,” _Navigation: Journal of The Institute of Navigation_ , Vol. 58, No. 3, 2011, pp. 187–201.  10.1007/s11263-008-0152-6.
  * Liebe [1995] Liebe, C. C., “Star Trackers for Attitude Determination,” _IEEE Aerospace and Electronic Systems Magazine_ , Vol. 10, No. 6, 1995, pp. 10–16.  10.1109/62.387971.
  * Liebe [2002] Liebe, C. C., “Accuracy Performance of Star Trackers — A Tutorial,” _IEEE Transactions on Aerospace and Electronic Systems_ , Vol. 38, No. 2, 2002, pp. 587–599.  10.1109/TAES.2002.1008988.
  * Christian and Crassidis [2021] Christian, J. A., and Crassidis, J. L., “Star Identification and Attitude Determination with Projective Cameras,” _IEEE Access_ , Vol. 9, 2021, pp. 25,768–25,794.  10.1109/ACCESS.2021.3054836.
  * El Hassan [2002] El Hassan, I. M., “Two-Dimensional Resection—A Survey Of Analytical Techniques,” _Australian Surveyor_ , Vol. 47, No. 1, 2002, pp. 14–23.  10.1080/00050356.2002.10558838.
  * Grunert [1841] Grunert, J. A., “Das Pothenot’sche Problem in erweiterter Gestalt; nebst Bemerkungen über seine Anwendungen in der Geodisie,” _Archiv der Mathematik und Physik_ , Vol. 1, 1841, pp. 238–248.
  * Haralick et al. [1994] Haralick, R. M., Lee, C., Ottenberg, K., and Nölle, M., “Review and Analysis of Solutions of the Three Point Perspective Pose Estimation Problem,” _International Journal of Computer Vision_ , Vol. 13, No. 3, 1994, pp. 331–356.  10.1007/BF02028352.
  * Gao et al. [2003] Gao, X., Hou, X., Tang, J., and Cheng, H., “Complete solution classification for the perspective-three-point problem,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , Vol. 25, No. 8, 2003, pp. 930–943.  10.1109/TPAMI.2003.1217599.
  * Tanygin [2014] Tanygin, S., “Closed-Form Solution for Lost-In-Space Visual Navigation Problem,” _Journal of Guidance, Control, and Dynamics_ , Vol. 37, No. 6, 2014, pp. 1754–1766.  10.2514/1.G000529.
  * Pascual-Escudero et al. [2021] Pascual-Escudero, B., Nayak, A., Briot, S., Kermorgant, O., Martinet, P., Safey El Din, M., and Chaumette, F., “Complete Singularity Analysis for the Perspective-Four-Point Problem,” _International Journal of Computer Vision_ , Vol. 129, 2021, pp. 1217–1237.  10.1007/s11263-020-01420-0.
  * Hartley and Zisserman [2003] Hartley, R., and Zisserman, A., _Multiple View Geometry, 2nd Ed._ , Cambridge University Press, Cambridge, UK, 2003, pp. 70–73,312–321.
  * Quan and Lan [1999] Quan, L., and Lan, Z., “Linear N-Point Camera Pose Estimation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , Vol. 21, No. 8, 1999, pp. 774–780.  10.1109/34.784291.
  * Ansar and Daniilidis [2003] Ansar, A., and Daniilidis, K., “Linear Pose Estimation from Points or Lines,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , Vol. 25, No. 5, 2003, pp. 578–589.  10.1109/TPAMI.2003.1195992.
  * Lepetit et al. [2009] Lepetit, V., Moreno-Noguer, F., and Fua, P., “EP$n$P: An Accurate $O(n)$ Solution to the P$n$P Problem,” _International Journal of Computer Vision_ , Vol. 81, 2009, pp. 155–166.  10.1007/s11263-008-0152-6.
  * Calhoun and Dabney [1995] Calhoun, P. C., and Dabney, R., “Solution to the problem of determining the relative 6 DOF state for spacecraft automated rendezvous and docking,” _Proc. SPIE_ , Vol. 2466, 1995, pp. 175–184.  10.1117/12.211505.
  * Crassidis et al. [2000] Crassidis, J. L., Alonso, R., and Junkins, J. L., “Optimal Attitude and Position Determination from Line-of-Sight Measurements,” _The Journal of the Astronautical Sciences_ , Vol. 48, 2000, pp. 391–408.  10.1007/BF03546286.
  * Besl and McKay [1992] Besl, P. J., and McKay, N. D., “A method for registration of 3-D shapes,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , Vol. 14, No. 2, 1992, pp. 239–256.  10.1109/34.121791.
  * Yang et al. [2021] Yang, H., Shi, J., and Carlone, L., “TEASER: Fast and Certifiable Point Cloud Registration,” _IEEE Transactions on Robotics_ , Vol. 37, No. 2, 2021, pp. 314–333.  10.1109/TRO.2020.3033695.
  * Nardone et al. [1984] Nardone, S. C., Lindgren, A. G., and Gong, K. F., “Fundamental properties and performance of conventional bearings-only target motion analysis,” _IEEE Transactions on Automatic Control_ , Vol. 29, No. 9, 1984, pp. 775–787.  10.1109/TAC.1984.1103664.
  * Harper [1955] Harper, R. B., “Pilot Boat Identification, Harbor Radar Systems,” _Navigation_ , Vol. 4, No. 5, 1955, pp. 195–201.  10.1002/j.2161-4296.1955.tb00164.x.
  * Casey [1888] Casey, J., _A sequel to the first six books of the Elements of Euclid, containing an easy introduction to modern geometry, with numerous examples_ , Hodges, Figgis & co., 1888, pp. 173–175.
  * Lindgren and Gong [1977] Lindgren, A. G., and Gong, K. F., “Position and Velocity Estimation Via Bearing Observations,” _IEEE Transactions on Aerospace and Electronic Systems_ , Vol. 14, No. 4, 1977, pp. 564–577.  10.1109/TAES.1978.308681.
  * Nardone and Aidala [1981] Nardone, S. C., and Aidala, V. J., “Observability Criteria for Bearings-Only Target Motion Analysis,” _IEEE Transactions on Aerospace and Electronic Systems_ , Vol. 17, No. 2, 1981, pp. 162–166.  10.1109/TAES.1981.309141.
  * Clohessy and Wiltshire [1960] Clohessy, W. H., and Wiltshire, R. S., “Terminal guidance system for satellite rendezvous,” _Journal of the Aerospace Sciences_ , Vol. 27, No. 9, 1960, pp. 653–658.  10.2514/8.8704.
  * Woffinden and Geller [2007] Woffinden, D. C., and Geller, D. K., “Navigating the Road to Autonomous Orbital Rendezvous,” _Journal of Spacecraft and Rockets_ , Vol. 44, No. 4, 2007, pp. 898–909.  10.2514/1.30734.
  * Semple and Kneebone [1952] Semple, J. G., and Kneebone, G. T., _Algebraic Projective Geometry_ , Oxford University Press, Oxford, UK, 1952.
  * Gallier [2011] Gallier, J., _Geometric Methods and Applications, 2nd Edition_ , Springer-Verlag, New York, 2011.
  * Christian et al. [2016] Christian, J., Benhacine, L., Hikes, J., and D’Souza, C., “Geometric Calibration of the Orion Optical Navigation Camera using Star Field Images,” _The Journal of the Astronautical Sciences_ , Vol. 63, No. 4, 2016, pp. 335–353.  10.1007/s40295-016-0091-3.
  * Bos and et al. [2020] Bos, B. J., and et al., “In-Flight Calibration and Performance of the OSIRIS-REx Touch And Go Camera System (TAGCAMS),” _Space Science Reviews_ , Vol. 71, 2020.  10.1007/s11214-020-00682-x.
  * Wahba [1965] Wahba, G., “A Least Square Estimate of Satellite Attitude,” _SIAM Review_ , Vol. 7, No. 3, 1965, p. 409.  10.1137/1007077.
  * Farrell et al. [1966] Farrell, J. L., Stuelpnagel, J. C., Wessner, R. H., Velman, J. R., and Brook, J. E., “A Least Squares Estimate of Satellite Attitude (Grace Wahba),” _SIAM Review_ , Vol. 8, No. 3, 1966, pp. 384–386.  10.1137/1008080.
  * Shuster and Oh [1981] Shuster, M. D., and Oh, S. D., “Three-Axis Attitude Determination from Vector Observations,” _Journal of Guidance and Control_ , Vol. 4, No. 1, 1981, pp. 70–77.  10.2514/3.19717.
  * Markley [1988] Markley, F. L., “Attitude Determination Using Vector Observations and the Singular Value Decomposition,” _The Journal of the Astronautical Sciences_ , Vol. 36, No. 3, 1988, pp. 245–258.
  * Shuster [1989] Shuster, M. D., “Maximum Likelihood Estimation of Spacecraft Attitude,” _The Journal of the Astronautical Sciences_ , Vol. 37, No. 1, 1989, pp. 79–88.
  * Mortari and Majji [2009] Mortari, D., and Majji, M., “Multiplicative Measurement Model,” _The Journal of the Astronautical Sciences_ , Vol. 57, No. 1 & 2, 2009, pp. 47–60.  10.1007/BF03321493.
  * Kaasalainen and Tanga [2004] Kaasalainen, M., and Tanga, P., “Photocentre offset in ultraprecise astrometry: Implications for barycentre determination and asteroid modelling,” _Astronomy and Astrophysics_ , Vol. 416, No. 1, 2004, pp. 367–373.  10.1051/0004-6361:20031711.
  * Olds and et al. [2022] Olds, R. D., and et al., “The Use of Digital Terrain Models for Natural Feature Tracking at Asteroid Bennu,” _The Planetary Science Journal_ , Vol. 3, 2022.  10.3847/PSJ/ac5184.
  * Lowe [2004] Lowe, D. G., “Distinctive Image Features from Scale-Invariant Keypoints,” _International Journal of Computer Vision_ , Vol. 60, No. 2, 2004, pp. 91–110.  10.1023/B:VISI.0000029664.99615.94.
  * Cheng et al. [2006] Cheng, Y., Crassidis, J. L., and Markley, F. L., “Attitude Estimation for Large Field-of-View Sensors,” _The Journal of the Astronautical Sciences_ , Vol. 54, No. 3 & 4, 2006, pp. 433–448.  10.1007/BF03256499.
  * Tūsī [1891] Tūsī, .-., Nasīr al-Dīn Muhammad ibn Muhammad, _Traitè du quadrilatère attribué a Nassiruddinel-Toussy, d’après un manuscrit tiré de la bibliothèque de S.A. Edhem Pacha_ , Typographie et lithographie Osmaniè, Turkey, 1891.
  * Aydin et al. [2020] Aydin, N., Hammoudi, L., and Bakbouk, G., _Al-Kashi’s Miftah al-Hisab, Volume II: Geometry_ , Birkhäuser Cham, 2020, p. 31.  10.1007/978-3-030-61330-3.
  * Abdel-Aziz and Karara [2015] Abdel-Aziz, Y. I., and Karara, H. M., “Direct Linear Transformation from Comparator Coordinates into Object Space Coordinates in Close-Range Photogrammetry,” _Photogrammetric Engineering & Remote Sensing_, Vol. 81, No. 2, 2015, pp. 103–107.  10.14358/PERS.81.2.103.
  * Christian [2019] Christian, J. A., “Autonomous Initial Orbit Determination with Optical Observations of Unknown Planetary Landmarks,” _Journal of Spacecraft and Rockets_ , Vol. 56, No. 1, 2019, pp. 211–220.  10.2514/1.A34259.
  * Gennery [1992] Gennery, D. B., _Calibration and Orientation of Cameras in Computer Vision_ , Springer, 1992, Chaps. Least-Squares Camera Calibration Including Lens Distortion and Automatic Editing of Calibration Points, pp. 47–48.  10.1007/978-3-662-04567-1_5.
  * K and Li [2004] K, D., and Li, R., “CAHVOR camera model and its photogrammetric conversion for planetary applications,” _Journal of Geophysical Research_ , Vol. 109, 2004.  10.1029/2003JE002199.
  * Plücker [1865] Plücker, J., “On a new geometry of space,” _Philosophical Transactions of the Royal Society_ , Vol. 155, 1865.  10.1098/rstl.1865.0017.
  * Bartoli and Sturm [2005] Bartoli, A., and Sturm, P., “Structure-from-motion using lines: Representation, triangulation, and bundle adjustment,” _Computer Vision and Image Understanding_ , Vol. 100, No. 3, 2005, pp. 416–441.  10.1016/j.cviu.2005.06.001.
  * Franzese and Topputo [2020] Franzese, V., and Topputo, F., “Optimal Beacons Selection for Deep-Space Optical Navigation,” _The Journal of the Astronautical Sciences_ , Vol. 67, 2020, pp. 1775–1792.  10.1007/s40295-020-00242-z.
  * Shuster [1990] Shuster, M. D., “Kalman Filtering of Spacecraft Attitude and the QUEST Model,” _The Journal of the Astronautical Sciences_ , Vol. 38, No. 3, 1990, pp. 377–393.
  * Fisher [1922] Fisher, R. A., “On the mathematical foundations of theoretical statistics,” _Philosophical Transactions of the Royal Society of London. Series A_ , Vol. 222, 1922, pp. 309–368.  10.1098/rsta.1922.0009.
  * Tapley et al. [2004] Tapley, B., Schutz, B., and Born, G., _Statistical Orbit Determination_ , Elsevier Academic Press, Amsterdam, 2004, pp. 172–173,190–194.  10.1016/B978-0-12-683630-1.X5019-X.
  * Hartley [1998] Hartley, R. I., “Chirality,” _International Journal of Computer Vision_ , Vol. 26, No. 1, 1998, pp. 41–61.  10.1023/A:1007984508483.
  * Armstrong [1996] Armstrong, M. N., “Self-Calibration from Image Sequences,” Ph.D. thesis, University of Oxford, 1996.
  * Sturm [1997] Sturm, P. F., “Vision 3D Non Calibrée: Contributions à la Reconstruction Projective et Étude des Mouvements Critiques pour L’Auti-Calibrage,” Ph.D. thesis, Institut National Polytechnique de Grenoble, 1997\.
  * Kobylka and Christian [2021] Kobylka, K. R., and Christian, J. A., “Methods in Triangulation for Image-Based Terrain Relative Navigation,” _AAS/AIAA Space Flight Mechanics Meeting_ , 2021.
  * Goulb and Van Loan [2013] Goulb, G. H., and Van Loan, C. F., _Matrix Computations, 4th Ed._ , Johns Hopkins University Press, 2013, pp. 260–268,304–306.
  * Aldrich [1997] Aldrich, J., “R. A. Fisher and the Making of Maximum Likelihood 1912–1922,” _Statistical Science_ , Vol. 12, No. 3, 1997, pp. 162–176.  10.1214/ss/1030037906.
  * Gelb [1974] Gelb, A., _Applied Optimal Estimation_ , MIT Press, Cambridge, MA, 1974.
  * Carr and Sobek [1980] Carr, J. R., and Sobek, J. S., “Digital Scene Matching Area Correlator (DSMAC),” _Proc. SPIE_ , Vol. 0238, 1980, pp. 36–41.  10.1117/12.959130.
  * Golden [1980] Golden, J. P., “Terrain Contour Matching (TERCOM): A Cruise Missile Guidance Aid,” _Proc. SPIE_ , Vol. 0238, 1980, pp. 10–18.  10.1117/12.959127.
  * Kim and Sukkarieh [2004] Kim, J., and Sukkarieh, S., “Autonomous airborne navigation in unknown terrain environments,” _IEEE Transactions on Aerospace and Electronic Systems_ , Vol. 40, No. 3, 2004, pp. 1031–1045.  10.1109/TAES.2004.1337472.
  * Cheng and Miller [2003] Cheng, Y., and Miller, J., “Autonomous landmark based spacecraft navigation system,” _AAS/AIAA Astrodynamics Specialist Conference_ , 2003\.
  * Y. Cheng and Ansar [2005] Y. Cheng, and Ansar, A., “Landmark Based Position Estimation for Pinpoint Landing on Mars,” _IEEE International Conference on Robotics and Automation_ , 2005, pp. 1573–1578.  10.1109/ROBOT.2005.1570338.
  * Adams et al. [2008] Adams, D., Criss, T., and Shankar, U., “Passive Optical Terrain Relative Navigation Using APLNav,” _IEEE Aerospace Conference_ , 2008, pp. 1–9.  10.1109/AERO.2008.4526303.
  * Steffes et al. [2019] Steffes, S. R., Monterroza, F., Benhacine, L., and Mario, C., “Optical Terrain Relative Navigation Approaches to Lunar Orbit, Descent and Landing,” _AIAA Scitech Forum_ , 2019.  10.2514/6.2019-1178.
  * Acton [1996] Acton, C., “Ancillary data services of NASA’s Navigation and Ancillary Information Facility,” _Planetary and Space Sciences_ , Vol. 44, No. 1, 1996, pp. 65–70.  10.1016/0032-0633(95)00107-7.
  * Acton et al. [2018] Acton, C., Bachman, N., Semenov, B., and Wright, E., “A look towards the future in the handling of space science mission geometry,” _Planetary and Space Sciences_ , Vol. 150, 2018, pp. 9–12.  10.1016/j.pss.2017.02.013.
  * Johnson et al. [2017] Johnson, A., Aaron, S., Chang, J., Cheng, Y., Montgomery, J., Mohan, S., Schroeder, S., Tweddle, B., Trawny, N., and Zheng, J., “The Lander Vision System for Mars 2020 Entry Descent and Landing,” _AAS Guidance Navigation and Control Conference_ , 2017.
  * Maki and et al. [2020] Maki, J. N., and et al., “The Mars 2020 Engineering Cameras and Microphone on the Perseverance Rover: A Next-Generation Imaging System for Mars Exploration,” _Space Science Reviews_ , Vol. 216, 2020.  10.1007/s11214-020-00765-9.
  * National Academies of Sciences, Engineering, and Medicine [2022] National Academies of Sciences, Engineering, and Medicine, _Origins, Worlds, and Life: A Decadal Strategy for Planetary Science and Astrobiology 2023-2032_ , The National Academies Press, 2022, pp. S–7.  10.17226/26522.
  * Jacobson [2014] Jacobson, R. A., “The Orbits of the Uranian Satellites and Rings, the Gravity Field of the Uranian System, and the Orientation of the Pole of Uranus,” _The Astronomical Journal_ , Vol. 148, No. 5, 2014.  10.1088/0004-6256/148/5/76.
  * Lubey et al. [2020] Lubey, D. P., Bhaskaran, S., Bradley, N., and Olikara, Z., “Ice Giant Exploration Via Autonomous Optical Navigation,” _AAS/AIAA Astrodynamics Specialist Conference_ , 2020.
  * Bruzelius [1987] Bruzelius, C., “The Construction of Notre-Dame in Paris,” _The Art Bulletin_ , Vol. 69, 1987, pp. 540–569.  10.1080/00043079.1987.10788458.
  * Snavely et al. [2006] Snavely, N., Seitz, S. M., and Szeliski, R., “Photo tourism: exploring photo collections in 3D,” _ACM SIGGRAPH_ , 2006.  10.1145/1179352.1141964.
  * Naasz and Moreau [2015] Naasz, B., and Moreau, M., “Autonomous RPOD Challenges for the Coming Decade,” _AAS Guidance Navigation and Control Conference_ , 2015.
  * Houbolt [1962] Houbolt, J. C., “Problems and Potentialities of Space Rendezvous,” _Space Flight and Re-Entry Trajectories_ , Springer, Vienna, 1962, pp. 406–429.  10.1007/978-3-7091-5470-0_6.
  * Young and Alexander [1970] Young, K. A., and Alexander, J. D., “Apollo Lunar Rendezvous,” _Journal of Spacecraft and Rockets_ , Vol. 7, No. 9, 1970, pp. 1083–1086.  10.2514/3.30106.
  * Goodman [2006] Goodman, J. L., “History of Space Shuttle Rendezvous and Proximity Operations,” _Journal of Spacecraft and Rockets_ , Vol. 43, No. 5, 2006, pp. 944–959.  10.2514/1.19653.
  * Mattingly et al. [2005] Mattingly, R., HAyati, S., and Udomkesmalee, G., “Technology development plans for the Mars Sample Return mission,” 2005.  10.1109/AERO.2005.1559389.
  * Reed et al. [2016] Reed, B. B., Smith, R. C., Naasz, B., and Pellegrino, J., “The Restore-L Servicing Mission,” _AIAA SPACE 2016 Forum_ , 2016.  10.2514/6.2016-5478.
  * Sullivan and D’Amico [2017] Sullivan, J., and D’Amico, S., “Nonlinear Kalman Filtering for Improved Angles-Only Navigation Using Relative Orbital Elements,” _Journal of Guidance, Control, and Dynamics_ , Vol. 40, No. 9, 2017, pp. 2183–2200.  10.2514/1.G002719.
  * Vallado [2007] Vallado, D., _Fundamentals of Astrodynamics and Applications, 3rd Ed._ , Microcosm Press, Hawthorne, CA, 2007, pp. 389–417.
  * Klein and Geller [2015] Klein, I., and Geller, D., “Zero $\Delta$V Solution to the Angles-Only Range Observability Problem during Orbital Proximity Operations,” _Itzhack Y. Bar-Itzhack Memorial Symposium on Estimation, Navigation, and Spacecraft Control_ , 2015, pp. 351–369.  10.1007/978-3-662-44785-7_19.


# A combinatorial proof of the Burdzy–Pitman conjecture

Stanisław Cichomski111Faculty of Mathematics, Informatics and Mechanics,
University of Warsaw (Poland). E-mail<EMAIL_ADDRESS>, Fedor
Petrov222St. Petersburg State University and St. Petersburg Department of the
Steklov Mathematical Institute RAS (Russia).
E-mail<EMAIL_ADDRESS>
###### Abstract

We prove a sharp upper bound for the number of high degree differences in
bipartite graphs: let $(U,V,E)$ be a bipartite graph with
$U=\\{u_{1},u_{2},\dots,u_{n}\\}$ and $V=\\{v_{1},v_{2},\dots,v_{n}\\}$; for
$n\geq k>\frac{n}{2}$ we show that

$\sum_{1\leq i,j\leq
n}\mathbbm{1}{\Big{\\{}|\mathrm{deg}(u_{i})-\mathrm{deg}(v_{j})|\geq
k}\Big{\\}}\leq 2k(n-k).$

As a direct application we show a slightly stronger, probabilistic version of
this theorem and thus confirm the Burdzy–Pitman conjecture about the maximal
spread of coherent and independent distributions.

##  1 Introduction

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space. We say that a
random vector $(X,Y)$ defined on this probability space, is coherent, if there
exist sub $\sigma$-fields $\mathcal{G},\mathcal{H}\subset\mathcal{F}$ and an
event $A\in\mathcal{F}$, such that

$X=\mathbb{E}(\mathbbm{1}_{A}|\mathcal{G}),\ \ \ \ \
Y=\mathbb{E}(\mathbbm{1}_{A}|\mathcal{H}).$

We will also say that the joint distribution of such $(X,Y)$ is coherent on
$[0,1]^{2}$. Hereinafter, we write $(X,Y)\in\mathcal{C}$ or
$\mu\in\mathcal{C}$ to indicate that the vector $(X,Y)$ or a distribution
$\mu$ is coherent. Although this notation might be seen as a bit ambiguous, it
does not lead to any misunderstandings.

Krzysztof Burdzy and Soumik Pal [1] prove that for any
$\delta\in(\frac{1}{2},1]$ and $(X,Y)\in\mathcal{C}$ the probability
$\mathbb{P}(|X-Y|\geq\delta)$ of the difference between coherent variables
exceeding a given threshold $\delta$ is bounded above by the quantity
$\frac{2(1-\delta)}{2-\delta}$. They go on to show that this bound is sharp
and it is attained by a random vector $(X,Y)$ with $X$ and $Y$ being dependent
random variables.

Let us denote

$\mathcal{C_{I}}=\\{(X,Y):X,Y\in\mathcal{C},\ X\perp Y\\},$

as a family of those coherent distributions, which are additionally
independent. In this paper we positively answer a related and very natural
question raised by Krzysztof Burdzy and Jim Pitman in [2], where they have
formulated the following conjecture:

######  Conjecture 1.1.

For $\delta\in(\frac{1}{2},1]$, we have

$\sup_{(X,Y)\in\mathcal{C}_{\mathcal{I}}}\mathbb{P}(|X-Y|\geq\delta)=2\delta(1-\delta).$
(1)

Let us highlight, that this formalism should be regarded as taking supremum
over all probability spaces $(\Omega,\mathcal{F},\mathbb{P})$, all events
$A\in\mathcal{F}$ and all pairs of independent sub $\sigma$-fields
$\mathcal{G},\mathcal{H}\subset\mathcal{F}$. Although there are known
alternative characterizations of coherent distributions [5, 6, 8], let us
quote [2]:

> For reasons we do not understand well, these general characterizations seem
> to be of little help in establishing the evaluations of $\epsilon(\delta)$
> [i.e. $\mathbb{P}(|X-Y|\geq\delta)$] discussed above, or in settling a
> number of related problems about coherent distributions […].

It is our belief that this is indeed so, because of the underlying
combinatorial nature of those problems. Notice that discretization and
combinatorial techniques appear already in [1, 4].

Let us briefly describe our approach and the organization of the paper. It is
a well-known fact that the properties of two-dimensional coherent vectors are
very similar to the properties of degree sequences of bipartite graphs.
Remarkable example of this phenomenon can be found in [10]. Therefore, in
order to take advantage of the combinatorial nature of the problem, we start
by discussing its graph-theoretic version. More precisely, in the next section
we prove the following theorem.

######  Theorem 1.1.

Let $G=(U,V,E)$ be a bipartite graph with an equal bipartition, i.e.

$U=\\{u_{1},u_{2},\dots,u_{n}\\},\ \ \ V=\\{v_{1},v_{2},\dots,v_{n}\\},$

for some $n\in\mathbb{Z}_{+}$. For $n\geq k>\frac{n}{2}$ we have

$\sum_{1\leq i,j\leq
n}\mathbbm{1}{\Big{\\{}|\mathrm{deg}(u_{i})-\mathrm{deg}(v_{j})|\geq
k}\Big{\\}}\ \leq\ 2k(n-k).$ (2)

The proof of the Theorem 1.1 is based on an idea similar to the spread
bounding theorem of Erdős et al. – see [7]. In Section $2$ we then provide an
elementary example showing that the bound (2) is sharp. In what follows in
Section $3$, we show how to reduce the initial problem to the Theorem 1.1. To
this end, we make use of an appropriate sampling construction, similar in
spirit to [9]. The key idea is to approximate a fixed coherent distribution
with a randomly generated sequence of graphs. We then apply Theorem 1.1 to
each of the graphs in the sequence and obtain (1) by passing to the limit.

##  2 Number of high degree differences in bipartite graphs

Let $G=(U,V,E)$ be a bipartite graph with an equal bipartition, that is a
triplet

$U=\\{u_{1},u_{2},\dots,u_{n}\\},\ \ \ V=\\{v_{1},v_{2},\dots,v_{n}\\},$

and

$E\subset U\times V,$

for some fixed $n\in\mathbb{Z}_{+}$. Let us also choose a natural number $k$
satisfying $n\geq k>\frac{n}{2}$. Hereinafter, we denote the degree sequences
of $G$ as $(\alpha_{i})_{i=1}^{n}$ and $(\beta_{j})_{j=1}^{n}$, i.e.
$\alpha_{i}=\mathrm{deg}(u_{i})$ and $\beta_{j}=\mathrm{deg}(v_{j})$ for all
$1\leq i,j\leq n$. Without loss of generality we also assume that

$\alpha_{1}\geq\alpha_{2}\geq\dots\geq\alpha_{n},$
$\beta_{1}\geq\beta_{2}\geq\dots\geq\beta_{n}.$

We start with an observation similar to the spread bounding theorem of Erdős
et al. – see [7].

######  Lemma 2.1.

There exist $s,t\in\\{1,2,\dots,n-k+1\\}$ such that
$\alpha_{s}\leq\beta_{s+k-1}+k-1$ and $\beta_{t}\leq\alpha_{t+k-1}+k-1$.

Proof: We will prove only the existence of $s$, as the case of $t$ is
analogous. Assume for the sake of contradiction that such a number $s$ does
not exists. Therefore, the total number of edges incident to
$u_{1},u_{2},\dots,u_{n-k+1}$ is at least
$\beta_{k}+\beta_{k+1}+\dots+\beta_{n}+k(n-k+1)$. Observe that at least
$k(n-k+1)$ of these edges go to vertices $v_{1},v_{2},\dots,v_{k-1}$. Let us
denote

$\tilde{E}:=E\cap\Big{(}\\{u_{1},u_{2},\dots,u_{n-k+1}\\}\times\\{v_{1},v_{2},\dots,v_{k-1}\\}\Big{)},$

and notice that we have just shown that $|\tilde{E}|\geq k(n-k+1)$. On the
other hand, we clearly have

$|\tilde{E}|\leq(k-1)(n-k+1),$

which is a contradiction. ∎

We now prove the Theorem 1.1. With this result, we establish a natural upper
bound on the number of possible pairs of vertices with high degree differences
in $G$.

Proof of Theorem 1.1: For $1\leq i,j\leq n$, let us call $(i,j)$ an
$\mathcal{A}$-pair if $\alpha_{i}\geq\beta_{j}+k$. Correspondingly, let us
call $(i,j)$ a $\mathcal{B}$-pair if $\beta_{j}\geq\alpha_{i}+k$. Since
$k>\frac{n}{2}$, we have $\alpha_{i}>\frac{n}{2}$ for all $\mathcal{A}$-pairs
$(i,j)$ and $\alpha_{i}<\frac{n}{2}$ for all $\mathcal{B}$-pairs $(i,j)$. As a
consequence, there exists an $i_{0}\in\\{1,2,\dots,n+1\\}$ such that:

  1. 1.

$i\leq i_{0}-1$ for any $\mathcal{A}$-pair $(i,j)$,

  2. 2.

$i\geq i_{0}$ for any $\mathcal{B}$-pair $(i,j)$.

Analogously, there exists $j_{0}\in\\{1,2,\dots,n+1\\}$ such that:

  1. 3.

$j\leq j_{0}-1$ for any $\mathcal{B}$-pair $(i,j)$,

  2. 4.

$j\geq j_{0}$ for any $\mathcal{A}$-pair $(i,j)$.

Observe that by the Lemma 2.1, we also have:

  1. 5.

for any $\mathcal{A}$-pair $(i,j)$ either $i<s$ or $j>s+k-1$,

  2. 6.

for any $\mathcal{B}$-pair pair $(i,j)$ either $j<t$ or $i>t+k-1$.

We now show that the restrictions $1$–$6$, regardless of the initial graph,
imply that the total number of $\mathcal{A}$-pairs and $\mathcal{B}$-pairs
together is at most $2k(n-k)$. Let us fix $i_{0},j_{0}\in\\{1,2,\dots,n+1\\}$.
First, we verify that the optimal values of $s$ and $t$ satisfy
$s,t\in\\{1,n-k+1\\}$.

Notice that the variable $s$ appears only in the $5$-th condition and thus the
value of $s$ is not important for bounding the number of $\mathcal{B}$-pairs.
Moreover, observe that if $i_{0}\leq n-k+1$, then for $s=n-k+1$ the condition
$5$. is automatically fulfilled and thus $s=n-k+1$ is an optimal value.
Similarly, if $j_{0}\geq k+1$, then for $s=1$ the condition $5$. is also
automatically fulfilled and $s=1$ is an optimal value. Finally, let us assume
that $i_{0}\geq n-k+2$ and $j_{0}\leq k$. In this case, the restrictions
imposed by the condition $5$. remove exactly $(i_{0}-s)(s+k-j_{0})$ additional
pairs. Therefore, as the last expression is a concave function of
$s\in[1,n-k+1]$, it is minimized in one of the endpoints. Hence we may assume
that $s=1$ or $s=n-k+1$, as desired. Analogously, we show that $t=1$ or
$t=n-k+1$ is optimal. There are four possible cases now:

  1. a.

$s=1,\ t=n-k+1$. We have $j\geq k+1$ for all $\mathcal{A}$-pairs and $j\leq
n-k$ for all $\mathcal{B}$-pairs $(i,j)$. Thus any $i$ participates in at most
$n-k$ of $\mathcal{A}$-pairs and in at most $n-k$ of $\mathcal{B}$-pairs.
Therefore, since a fixed vertex can not participate in both types of pairs,
every $i$ participates overall in at most $n-k$ pairs. As a consequence, the
total number of pairs does not exceed $n(n-k)<2k(n-k)$.

  2. b.

$s=n-k+1,\ t=1$. This case is symmetric to the previous one.

  3. c.

$s=1,\ t=1$. We have $j\geq k+1$ for all $\mathcal{A}$-pairs and $i\geq k+1$
for all $\mathcal{B}$-pairs $(i,j)$. Let us denote $a:=\max(k+1,j_{0})$ and
$b:=\max(k+1,i_{0})$. Then the total number of $\mathcal{A}$-pairs is bounded
by $(n-a+1)(b-1)$, while the total number of $\mathcal{B}$-pairs is at most
$(n-b+1)(a-1)$. Notice, that for $a,b\in[k+1,n+1]$ the sum

$S:=(n-a+1)(b-1)+(n-b+1)(a-1),$

is bilinear and it is maximized at one of four endpoints. For $a=b=k+1$, we
get $S=2k(n-k)$. For, say $a=n+1$, we get $S=n(n-b+1)\leqslant
n(n-k)<2k(n-k)$.

  4. d.

$s=n-k+1,\ t=n-k+1$. This case is analogous to c.

Hence we have shown that the Theorem 1.1 holds in all cases. This ends the
proof. ∎

We end this section with an example showing that the upper bound $2k(n-k)$ in
(2) cannot be improved. Note that a straightforward modification of this
example shows that $2\delta(1-\delta)$ in (1) is also sharp.

######  Example 2.1.

Consider $n,k\in\mathbb{Z}_{+}$, with $n\geq k>\frac{n}{2}$. Let
$G_{n,k}=(U,V,E)$, where $U=V=\\{1,2,\dots,n\\}$ and

$E\ =\ \\{(u,v)\in U\times V:\ \max(u,v)\leq k\\}.$

We clearly have

$\sum_{1\leq i,j\leq
n}\mathbbm{1}{\Big{\\{}|\mathrm{deg}(u_{i})-\mathrm{deg}(v_{j})|\geq
k}\Big{\\}}\ =\ 2k(n-k).$

Moreover, one can check that inequality (2) becomes an equality exactly for
those graphs $G$ that are isomorphic to $G_{n,k}$ or to its complement
$\overline{G}_{n,k}$. This follows easily from the proof of Theorem 1.1 and we
leave the details to interested reader.

##  3 Proof of the Burdzy–Pitman conjecture

By $\mathcal{C}_{\mathcal{I}}(n)$ we denote the set of those
$(X,Y)\in\mathcal{C}_{\mathcal{I}}$, that both $X$ and $Y$ take at most $n$
different values.

######  Proposition 3.1.

Let $(X,Y)$ be coherent and independent, and let $n$ be a positive integer.
Then there exists $(X_{n},Y_{n})\in\mathcal{C}_{\mathcal{I}}(n)$, such that
$|X-X_{n}|\leq\frac{1}{n}$ and $|Y-Y_{n}|\leq\frac{1}{n}$, almost surely.

The proof of the above Proposition can be found in [3, 1]. In what follows,
fix any $\delta\in(\frac{1}{2},1]$.

######  Proposition 3.2.

To prove the Conjecture 1.1 it is enough to verify it for $\
\bigcup_{n=1}^{\infty}\mathcal{C}_{\mathcal{I}}(n)$.

Proof: Fix $(X,Y)\in\mathcal{C}_{\mathcal{I}}$ and choose $(X_{n},Y_{n})$ as
in Proposition 3.1. By the triangle inequality we get

$\mathbb{P}(|X-Y|\geq\delta)\ \leq\ \mathbb{P}(|X_{n}-Y_{n}|\geq\delta-2/n).$

Thus, assuming that the Conjecture 1.1 is true for $\
\bigcup_{n=1}^{\infty}\mathcal{C}_{\mathcal{I}}(n)$, for $n$ large enough we
obtain

$\mathbb{P}(|X-Y|\geq\delta)\ \leq\ 2(\delta-2/n)(1-\delta+2/n).$

Passing to the limit ends the proof. ∎

We are now able to prove our main result.

Proof of Conjecture 1.1: Fix
$(X,Y)\in\bigcup_{n=1}^{\infty}\mathcal{C}_{\mathcal{I}}(n)$. There exists a
probability space $(\Omega,\mathcal{F},\mathbb{P})$, independent sub
$\sigma$-fields $\mathcal{G},\mathcal{H}\subset\mathcal{F}$ and an event
$A\in\mathcal{F}$, such that $X=\mathbb{E}(\mathbbm{1}_{A}|\mathcal{G})$ and
$Y=\mathbb{E}(\mathbbm{1}_{A}|\mathcal{H})$. Furthermore, for some
$N,M\in\mathbb{Z}_{+}$, we may suppose that $X$ takes values
$x_{1},x_{2},\dots,x_{N}$ on sets $G_{1},G_{2},\dots,G_{N}$, respectively of
the probability space $(\Omega,\mathcal{F},\mathbb{P})$, and $Y$ takes values
$y_{1},y_{2},\dots,y_{M}$ on sets $H_{1},H_{2},\dots,H_{M}$. For simplicity,
we can also assume that

$\mathcal{G}=\sigma\Big{(}G_{1},G_{2},\dots,G_{N}\Big{)},$
$\mathcal{H}=\sigma\Big{(}H_{1},H_{2},\dots,H_{M}\Big{)},$

meaning that $\sigma$-fields $\mathcal{G},\mathcal{H}$ are generated by those
disjoint partitions of $\Omega$. For $1\leq i\leq N$ and $1\leq j\leq M$,
denote the probabilities $p_{i}=\mathbb{P}(G_{i}),q_{j}=\mathbb{P}(H_{j})$ and

$\rho_{i,j}=\frac{\mathbb{P}(G_{i}\cap H_{j}\cap A)}{\mathbb{P}(G_{i}\cap
H_{j})}.$

Then by the independence we have $\mathbb{P}(G_{i}\cap H_{j})=p_{i}q_{j}$ and

$x_{i}=\sum_{j=1}^{M}q_{j}\rho_{i,j},\ \ \ \ \ \ 1\leq i\leq N,$ (3)
$y_{j}=\sum_{i=1}^{N}p_{i}\rho_{i,j},\ \ \ \ \ \ 1\leq j\leq M,$ (4)

which follows from a direct computation.

First, we show how to construct a sequence of bipartite graphs
$G_{n}=(U_{n},V_{n},E_{n})$ with $|U_{n}|=|V_{n}|=n$, such that:

  1. 1.

in $U_{n}$ we have $p_{i}n+O(n^{3/4})$ vertices of degree $x_{i}n+O(n^{3/4})$,
$i=1,2,\dots,N$,

  2. 2.

in $V_{n}$ we have $q_{j}n+O(n^{3/4})$ vertices of degree $y_{j}n+O(n^{3/4})$,
$j=1,2,\dots,M$,

where by $O(n^{3/4})$ we denote any quantity bounded in magnitude by
$Cn^{3/4}$ for some absolute constant $C>0$, which is uniform in $i$ and $j$.

To this end, let us fix $n$ and without loss of generality assume that $n$ is
large. We choose $n$ independent points $u_{1},u_{2},\dots,u_{n}$ in our
probability space $(\Omega,\mathcal{F},\mathbb{P})$ and for $1\leq i\leq n$
denote $\alpha_{i}=s$ if $u_{i}\in G_{s}$. In other words,
$(\alpha_{1},\alpha_{2},\dots,\alpha_{n})$ is an i.i.d. sample from the set
$\\{1,2,\dots,N\\}$ with weights $p_{1},p_{2},\dots,p_{N}$, respectively. We
can think about this sample as a randomly generated sequence of labels. Let
$A_{s}=\sum_{i=1}^{n}\mathbbm{1}_{\\{\alpha_{i}=s\\}}$ be the number of labels
equal to $s$, $1\leq s\leq N$. Observe that $A_{s}$ is clearly a sum of $n$
independent Bernoulli random variables. Hence, by the well known Hoeffding’s
inequality, we have

$\mathbb{P}(|A_{s}-np_{s}|\geq nr)\ \leq\ 2\cdot e^{-2nr^{2}},$

for all positive $r$. Consequently, setting $r=n^{-1/4}$ we get

$\mathbb{P}(|A_{s}-np_{s}|\geq n^{3/4})\ \leq\ 2\cdot e^{-2\sqrt{n}}.$

Thus, as $n$ is large, with high probability we have $A_{s}=np_{s}+O(n^{3/4})$
for all $1\leq s\leq N$. In fact, if this would not be the case, we can always
reject the labels $(\alpha_{1},\alpha_{2},\dots,\alpha_{n})$ and resample them
again. Analogously, we choose points $v_{1},v_{2},\dots,v_{n}$ and generate an
i.i.d. sample $(\beta_{1},\beta_{2},\dots,\beta_{n})$ from the set
$\\{1,2,\dots,M\\}$ with weights $q_{1},q_{2},\dots,q_{M}$, respectively.
Next, let $B_{t}=\sum_{j=1}^{n}\mathbbm{1}_{\\{\beta_{j}=t\\}}$ be the number
of labels equal to $t$, $1\leq t\leq M$. As previously, we can further assume
that $B_{t}=nq_{t}+O(n^{3/4})$ for all $t$.

Next, conditioned on the labels $(\alpha_{i})_{i=1}^{n}$ and
$(\beta_{j})_{j=1}^{n}$, we generate a random bipartite grah
$(U_{n},V_{n},E_{n})$:

  1. 1.

for $1\leq i,j\leq n$ independently, generate an idicator variable $Z_{i,j}$
with

$\mathbb{P}_{\alpha,\beta}(Z_{i,j}=1)=1-\mathbb{P}_{\alpha,\beta}(Z_{i,j}=0)=\rho_{\alpha_{i},\beta_{j}},$

where
$(\Omega_{\alpha,\beta},\mathcal{F}_{\alpha,\beta},\mathbb{P}_{\alpha,\beta})$
is a new space on which such independent $(Z_{i,j})_{i,j}$ can be constructed.

  2. 2.

for $1\leq i,j\leq n$, set $(u_{i},v_{j})\in E_{n}$ iff $Z_{i,j}=1$,

or equivalently, let $Z_{i,j}=\mathbbm{1}_{\\{(u_{i},v_{j})\in E_{n}\\}}$. For
$1\leq i\leq n$, we can now write

$\mathbb{E}_{\alpha,\beta}\ \mathrm{deg}(u_{i})\ =\
\mathbb{E}_{\alpha,\beta}\Bigg{(}\sum_{j=1}^{n}Z_{i,j}\Bigg{)}\ =\
\sum_{t=1}^{M}B_{t}\rho_{\alpha_{i},t}\ =\
\sum_{t=1}^{M}\Big{(}nq_{t}+O(n^{3/4})\Big{)}\rho_{\alpha_{i},t},$

and hence

$\mathbb{E}_{\alpha,\beta}\ \mathrm{deg}(u_{i})\ =\
nx_{\alpha_{i}}+O(n^{3/4}),$ (5)

where the last line follows from (3). Similarilly, for $1\leq j\leq n$, by (4)
we get

$\mathbb{E}_{\alpha,\beta}\ \mathrm{deg}(v_{j})\ =\
ny_{\beta_{j}}+O(n^{3/4}).$ (6)

Lastly, again by the Hoeffdings’s inequality, we have

$\mathbb{P}_{\alpha,\beta}\Big{(}|\mathrm{deg}(u_{i})-\mathbb{E}_{\alpha,\beta}\
\mathrm{deg}(u_{i})|\geq n^{3/4}\Big{)}\ \leq\ 2\cdot e^{-2\sqrt{n}},$ (7)

and

$\mathbb{P}_{\alpha,\beta}\Big{(}|\mathrm{deg}(v_{j})-\mathbb{E}_{\alpha,\beta}\
\mathrm{deg}(v_{j})|\geq n^{3/4}\Big{)}\ \leq\ 2\cdot e^{-2\sqrt{n}},$ (8)

for all $i,j\in\\{1,2,\dots,n\\}$. Note that the concentration rates (7) and
(8) are exponential in $\sqrt{n}$. Thus, since $n$ is large, with high
probability all these concentrations take place. Then, by (5) and (6), we have
$\mathrm{deg}(u_{i})=nx_{\alpha_{i}}+O(n^{3/4})$ and
$\mathrm{deg}(v_{j})=ny_{\beta_{j}}+O(n^{3/4})$ for all
$i,j\in\\{1,2,\dots,n\\}$. This, together with bounds on $(A_{s})_{s=1}^{N}$
and $(B_{t})_{t=1}^{M}$, proves that $G_{n}$ does indeed satisfy the
structural conditions stated.

In what follows, we add additional subscripts and write $u_{i}^{(n)}$ and
$v_{j}^{(n)}$ for generic elements of $U_{n}$ and $V_{n}$, respectively. We
can now write

$\mathbb{P}(|X-Y|\geq\delta)\ =\ \sum_{\begin{subarray}{c}1\leq i\leq N\\\
1\leq j\leq M\end{subarray}}\mathbbm{1}_{\\{|x_{i}-y_{j}|\geq\delta\\}}\cdot
p_{i}q_{j}$ $=\ \lim_{n\to\infty}\
\frac{1}{n^{2}}\sum_{\begin{subarray}{c}1\leq i\leq N\\\ 1\leq j\leq
M\end{subarray}}\mathbbm{1}_{\\{|nx_{i}-ny_{j}|\geq
n\delta\\}}\cdot\Big{(}p_{i}n+O(n^{3/4})\Big{)}\Big{(}q_{j}n+O(n^{3/4})\Big{)}.$
(9)

Observe, that by the triangle inequality and defining properties of
$G_{n}=(U_{n},V_{n},E_{n})$, we have

$|nx_{\alpha_{i}}-ny_{\beta_{j}}|\ \leq\
|\mathrm{deg}(u_{i}^{(n)})-\mathrm{deg}(v_{j}^{(n)})|+2\cdot O(n^{3/4}),$

for all $i,j\in\\{1,2,\dots,n\\}$. Thus, we can further estimate the bound (9)
by

$\leq\ \limsup_{n\to\infty}\ \frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}\mathbbm{1}\Big{\\{}|\mathrm{deg}(u_{i}^{(n)})-\mathrm{deg}(v_{j}^{(n)})|\geq
n\delta-2O(n^{3/4})\Big{\\}}.$

Finally, applying Theorem 1.1 to each of the bipartite graphs $G_{n}$, we
obtain

$\leq\ \limsup_{n\to\infty}\ \frac{1}{n^{2}}\cdot
2\Big{(}n\delta-2O(n^{3/4})\Big{)}\Big{(}n-n\delta+2O(n^{3/4})\Big{)}\ =\
2\delta(1-\delta),$

which ends the proof. ∎

### Acknowledgments.

The work of the second-named author is supported by _Junior Leader_ grant of
Theoretical Physics and Mathematics Advancement Foundation ‘‘BASIS’’.

## References

  * [1] K. Burdzy and S. Pal.  Can coherent predictions be contradictory?  Advances in Applied Probability, 53, 2021.
  * [2] K. Burdzy and J. Pitman.  Bounds on the probability of radically different opinions.  Electron. Commun. Probab., 25, 2020.
  * [3] S. Cichomski.  Maximal spread of coherent distributions: a geometric and combinatorial perspective.  Master’s thesis, University of Warsaw, 2020.  available at arXiv:2007.08022 [math.PR].
  * [4] S. Cichomski and A. Os  ˛
---
ekowski.  The maximal difference among expert’s opinions.  Electronic Journal
of Probability, 26, 2021.

  * [5] A. P. Dawid, M. H. DeGroot, and J. Mortera.  Coherent combination of experts’ opinions.  Test, 4, 1995.
  * [6] L. E. Dubins and J. Pitman.  A maximal inequality for skew fields.  Zeitschrift fűr Wahrscheinlichkeitstheorie und Verwandte Gebiete, 52, 1980.
  * [7] P. Erdős, G. Chen, C.C. Rousseau, and R.H. Schelp.  Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs.  European Journal of Combinatorics, 14, 1993.
  * [8] S. Gutmann, J. H. B. Kemperman, J. A. Reeds, and L. A. Shepp.  Existence of probability measures with given marginals.  The Annals of Probability, 19, 1991.
  * [9] L. Lovász.  Large Networks and Graph Limits.  American Mathematical Society, 2012.
  * [10] T. Tao.  Szemerédi’s regularity lemma revisited.  Contributions to Discrete Mathematics, 1, 2006.