The University of
Sydneyjoachim.gudmundsson@sydney.edu.auhttps://orcid.org/0000-0002-6778-7990
Funded by the Australian Government through the Australian Research Council
DP180102870. The University of
Sydneyzijin.huang@sydney.edu.auhttps://orcid.org/0000-0003-3417-5303 The
University of<EMAIL_ADDRESS>Joachim Gudmundsson, Zijin Huang
and Sampson Wong [100]Theory of computation Design and analysis of algorithms
John Q. Open and Joan R. Access 2 42nd Conference on Very Important Topics
(CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging, United
Kingdom 42 23

# Approximating the $\lambda$-low-density value

Joachim Gudmundsson  Zijin Huang  Sampson Wong

###### Abstract

The use of realistic input models has gained popularity in the theory
community. Assuming a realistic input model often precludes complicated
hypothetical inputs, and the analysis yields bounds that better reflect the
behaviour of algorithms in practice.

One of the most popular models for polygonal curves and line segments is
$\lambda$-low-density. To select the most efficient algorithm for a certain
input, one often needs to compute the $\lambda$-low-density value, or at least
an approximate value. In this paper, we show that given a set of $n$ line
segments in $\mathbb{R}^{2}$ one can compute a $3$-approximation of the
$\lambda$-low density value in $O(n\log n+\lambda n)$ time. We also show how
to maintain a $3$-approximation of the $\lambda$-low density value while
allowing insertions of new segments in $O(\log n+\lambda^{2})$ amortized time
per update.

Finally, we argue that many real-world data sets have a small $\lambda$-low
density value, warranting the recent development of specialised algorithms.
This is done by computing approximate $\lambda$-low density values for $12$
real-world data sets.

###### keywords:

realistic input models, packedness, low density, computational geometry

##  1 Introduction

When designing algorithms, researchers often use worst-case analysis to show
the theoretical upper bound of their algorithms. The drawback of this approach
is that these worst-case cases are often convoluted, and they are unlikely to
occur in practice. Realistic input models attempt to rectify this issue by
placing realistic constraints on the input, resulting in an analysis that
better reflects the real-world performance.

There have been many proposed realistic models for geometric data including
fatness, low density, uncluttered, simple cover, and packedness [4, 5, 15], to
name a few. These models place realistic constraints on the input. We give
three examples of difficult computational tasks that become much more
tractable under realistic input constraints.

In the case of calculating the Fréchet distance, Bringmann [1] showed a lower
bound of $\Omega(n^{2-\epsilon})$ for computing a $(2-\epsilon)$-approximation
of the Fréchet distance between two polygonal curves assuming the Strong
Exponential Time Hypothesis (SETH). SETH asserts that $k$-SAT cannot be solved
in $O((2-\epsilon)^{n})$ time for any constant $\epsilon>0$, and $k$-SAT is an
NP-complete problem. SETH is a popular conjecture, and it implies that there
is no strongly subquadratic time algorithm to calculate the Fréchet distance.
However, Driemel et al. [5] showed a near-linear time
$(1+\epsilon)$-approximation algorithm in the case when the (polygonal) curves
are $c$-packed or $\lambda$-low density. A curve $\pi$ is $c$-packed if the
total length of $\pi$ inside any ball of radius $r$ is at most $c\cdot r$, and
a set of objects is $\lambda$-low-density if for any ball of any size, the
number of objects whose size is greater than the radius of the ball that
intersect the ball is at most $\lambda$.

In another instance, Van der Stappen [15] introduced $\lambda$-low-density as
a realistic assumption for obstacles in robotic navigation. Real-life
geometric structures, such as floor plans [14] and street maps [2] are often
low-density environments, and many robotic navigation problems can be solved
more efficient if the environment is assumed to be low-density [16].

Chen et al. [2] combined low density and packedness to produce a faster map-
matching algorithm. Given a polygonal curve $\pi$ and a graph $G$ with edges
embedded as straight line segments, they considered the problem of matching
$\pi$ to a path $P$ in $G$ that minimises the Fréchet distance between $\pi$
and $P$. Assuming that $G$ is $\lambda$-low-density, and $\pi$ is $c$-packed,
their algorithm runs in near-linear time. Furthermore, they verified that the
maps of San Francisco, Athens, Berlin, and San Antonio are all $\lambda$-low-
density where $\lambda$ is a small constant.

Although we can produce fast algorithms by assuming that the data set fits in
one of the realistic input models, how can we check if these assumptions are
reasonable? Researchers either assume that the majority of a particular type
of data set fits into one of the models (floor plans [14], and obstacles [16])
or use slow methods to verify existing data sets (English handwriting [5], and
city maps [2]). Such methods may not be suitable given the proliferation of
geometric data that is nowadays generated, and often in a dynamic setting.

Therefore, in this paper, we study the problem of deciding the $\lambda$-low-
density of a given set of segments in the Euclidean plane.

To the best of our knowledge, the algorithm by De Berg et al. [4] is the
current state-of-the-art for deciding the density value of a set of objects,
and takes $O(n\log^{3}n+\lambda n\log^{2}n+\lambda^{2}n)$ time [4]. However,
their algorithm can only handle the restricted case when segments do not
intersect. Furthermore, no data structure is known that allows for dynamic
update on the $\lambda$-low-density value.

The main result of this paper is: Given a set of $n$ line segments in
$\mathbb{R}^{2}$ one can compute a $3$-approximation of the $\lambda$-low
density value in $O(n\log n+\lambda n)$ time. We also show how to maintain a
$3$-approximation of the $\lambda$-low density value while allowing insertions
of new segments in $O(\log n+\lambda^{2})$ amortized time per update.

To investigate the usefulness of the $\lambda$-low density model for
trajectories we implemented a $4$-approximation algorithm to estimate the
density values of twelve real-world data sets. The median density values in
eleven of the data sets are less than $51$. The median $\lambda/n$ ratios of
six data sets are less than $0.04$, where $n$ is the size of the curve.
Although there are only twelve data sets and our values are estimates, the
results indicate that low density is a practical, realistic model for many
real-world data sets.

Due to the space constraint, some of the proofs can be found in the appendix.

##  2 Approximation algorithms

In this section, we show a simple quadratic time 25-approximation algorithm to
compute the density value of a given set of segments, which will then be
improved upon in later sections. We start by formally defining low density for
segments (see also Figure 1).

Figure 1: The set of segments in the figure is $4$-low-density. Segments
$s_{1}$ and $s_{2}$ touches $B$, while $s_{3}$ does not count as intersecting
$B$ since $|s_{3}|<\text{radius}(B)$. The ball $B$ is an optimal ball as it
intersects four segments, and no ball can intersect five or more segments.

######  Definition 2.1.

Let $S:=\\{s_{1},...,s_{n}\\}$ be a set of segments, and let $\lambda\geq 0$
be a parameter. We say $S$ is $\lambda$-low-density if for any ball $B$, the
number of segments $s_{i}\in S$ with $|s_{i}|\geq$ radius($B$) that intersect
$B$ is at most $\lambda$.

To simplify the description of the algorithms and the proofs we say a segment
$s$ _intersects_ a ball $B$ if and only if the length of
$|s|\geq\text{radius}($B$)$ and $s\cap B\neq\emptyset$, and $s$ is said to
_touch_ a ball $B$ if $s$ intersects $B$ at a single point. Finally, a ball
$B$ is optimal with respect to a set $S$ of segments if $S$ is $\lambda$-low-
density and $B$ intersects exactly $\lambda$ segments of $S$.

###  2.1 Basic properties and a first algorithm

In this section we will prove some basic properties that will lead us to a
simple approximation algorithm.

######  Lemma 2.2.

Let a set $S$ of segments in $\mathbb{R}^{2}$ be $\lambda$-low-density. There
exists an optimal ball $B$ and a segment $s$ intersecting $B$ such that
$|s|=\text{radius}(B)$, and $s$ is the shortest segment that intersect $B$.

######  Proof 2.3.

Let $B$ be an optimal ball that intersect with $\lambda$ segments. Let $s$ be
the shortest segment that intersects $B$. If $|s|=\text{radius}(B)$, we are
done. If $\left\lvert s\right\rvert>\text{radius}(B)$, then let $B^{\prime}$
be a ball with the same center as $B$, and let
$\text{radius}(B^{\prime})=|s|$. Then $B^{\prime}$ still intersects $\lambda$
segments. If $\left\lvert s\right\rvert<\text{radius}(B)$, then $s$ does not
intersect $B$ which contradicts the assumption.

Given Lemma 2.2, if $s$ is the shortest segment that intersect an optimal ball
$B$, then it immediately follows that $B$ must lie entirely within a stadium-
shaped region $P_{s}$ around $s$. That is, given a segment $s$, let $P_{s}$ be
the union of all points within distance $2\left\lvert s\right\rvert$ of a
point on $s$, as shown in Figure 2(a).

Figure 2: (a) A segment $s$ and its stadium $P_{s}$. (b) $Q_{s}$ covers
$P_{s}$.

Next, we show that $P_{s}$ can be covered by a $5\left\lvert s\right\rvert$ by
$5\left\lvert s\right\rvert$ axis-aligned square $Q_{s}$ centered at the
middle point of $s$, and $Q_{s}$ can be partitioned into 25 smaller squares of
side length $\left\lvert s\right\rvert$. Each of these smaller squares can be
covered by a ball of radius $\left\lvert s\right\rvert$. As a result, if there
exists an optimal ball $B$ intersecting $s$ and having radius $|s|$ then there
exists a small ball that intersects at least $\lambda/25$ segments.

The above arguments suggests a natural $O(n^{2})$ algorithm. By generating
$25$ balls per segment and calculating the maximum number of segments that
intersect any ball, we can compute a $25$-approximation of the density value
of a set of segments. The approach is outlined in Algorithm 1.

Algorithm 1 A 25-approximation algorithm

1:$S$: a set of segments in $\mathbb{R}^{2}$

2:$\lambda\leftarrow 0$

3:for each $s\in S$ do

4: $S^{\prime}\leftarrow$ the set of segments that intersect $Q_{s}$

5: $balls\leftarrow 25$ balls that covers $Q_{s}$

6: for each
$\mathord{\mathchoice{\leavevmode\resizebox{}{6.75pt}{\leavevmode\hbox{\set@color\raisebox{0.0pt}{$\displaystyle\bigcirc$}}}}{\leavevmode\resizebox{}{6.75pt}{\leavevmode\hbox{\set@color\raisebox{0.0pt}{$\textstyle\bigcirc$}}}}{\leavevmode\resizebox{}{4.72499pt}{\leavevmode\hbox{\set<EMAIL_ADDRESS>in $balls$ do

7: $\lambda\leftarrow$ max($\lambda$, the number of segments in $S^{\prime}$
that intersect
$\mathord{\mathchoice{\leavevmode\resizebox{}{6.75pt}{\leavevmode\hbox{\set@color\raisebox{0.0pt}{$\displaystyle\bigcirc$}}}}{\leavevmode\resizebox{}{6.75pt}{\leavevmode\hbox{\set@color\raisebox{0.0pt}{$\textstyle\bigcirc$}}}}{\leavevmode\resizebox{}{4.72499pt}{\leavevmode\hbox{\set<EMAIL_ADDRESS>
8:return $\lambda$

From the above arguments, we can also bound the number of segments that
intersect $Q_{s}$ which will be used in Section 3 to speed up the algorithm.

######  Corollary 2.4.

Let $S$ be a set of $\lambda$-low-density segments. For any $s\in S$, the
number of segments $s^{\prime}\in S$ with $\left\lvert
s^{\prime}\right\rvert\geq\left\lvert s\right\rvert$ that intersect $Q_{s}$ is
$O(\lambda)$.

###  2.2 Improving the approximation factor to three

In the previous section we gave a simple approximation algorithm with a rough
approximation factor for ease of explanation. The main idea of the
$25$-approximation algorithm is to cover the stadium $P_{s}$ with a square
grid containing $25$ small squares, and then cover each square with a ball.
This guarantees that there exists one ball that intersects at least
$\lambda/25$ segments.

In this section we will instead use a sheared triangular grid $G_{T}$ of
equilateral triangles having side length $|s|/9$. The sheared grid will have
side length $10|s|\times 10|s|$ and will be centered at the middle point of a
segment $s$. Note that the sheared grid covers the stadium $P_{s}$, as
illustrated in Fig. 3.

Figure 3: Illustrating the sheared $10|s|\times 10|s|$ triangular grid $G_{T}$
of equilateral triangles having side length $|s|/9$.

We will argue that for every triangle $T$ in the grid one can construct three
balls of radius $|s|$ such that any optimal ball of radius $|s|$ and center
within $T$, can be covered by three three balls. This will reduce the
approximation factor to $3$, while only increasing the running time by a
constant factor (due to increasing the number of balls we need to check). We
formally define the set of balls that cover $Q_{s}$. For an arbitrary triangle
$T$ in $G_{T}$, without loss of generality, assume that the bottom side of $T$
aligns with the $x$-axis, and let $(x,y)$ be $T$’s center. We place three
balls of radius $\left\lvert s\right\rvert$ centered at
$(x-(\frac{\sqrt{3}}{4}+\frac{1}{36})|s|,y-(\frac{1}{4}+\frac{1}{36\sqrt{3}})|s|)$,
$(x,y-(\frac{1}{2}+\frac{1}{18\sqrt{3}})|s|)$, and
$(x+(\frac{\sqrt{3}}{4}+\frac{1}{36})|s|,y+(\frac{1}{4}+\frac{1}{36\sqrt{3}})|s|)$,
respectively. We denote the set of balls constructed from the triangular grid
for $s$ with $\mathcal{B}_{s}$.

We first describe, in Observation 2.5, the region where an optimal ball can
exist. Let $P,Q\subseteq\mathbb{R}^{d}$. We denote Minkowski sum [17] by
$P\oplus Q=\\{p+q\mid p\in P,q\in Q\\}$. Note the following observation:

######  Observation 2.5.

Let $Q\subseteq\mathbb{R}^{d}$, $Q\neq\emptyset$, let $B_{0}$ be a ball of
radius $|s|$ centered at the origin, and let $B$ be a ball of radius $|s|$. If
$\text{center}(B)\in Q$, then $B\subseteq Q\oplus B_{0}$.

Using Observation 2.5 we can improve the approximation factor to three. It
suffices to to show that the Minkowski sum of a region and $B_{0}$ can be
covered by three balls in $\mathcal{B}_{s}$.

######  Lemma 2.6.

Let $T$ be an equilateral triangle in $G_{T}$, and let $B_{0}$ be a ball with
radius $|s|$ centered at the origin. There exists three balls in
$\mathcal{B}_{s}$ whose union cover $T\oplus B_{0}$.

######  Proof 2.7.

Consider an optimal ball $B$ of radius $|s|$, and let $T$ be the equilateral
triangle containing the centre of $B$. Without loss of generality, assume that
the bottom side of $T$ aligns with $x$-axis and let $(x,y)$ be the center of
$T$.

From the definition of the set $\mathcal{B}_{s}$ we know there exists three
balls $A$, $B$, and $C$ in $\mathcal{B}_{s}$ centered at
$(x-(\frac{\sqrt{3}}{4}+\frac{1}{36})|s|,y-(\frac{1}{4}+\frac{1}{36\sqrt{3}})|s|)$,
$(x,y-(\frac{1}{2}+\frac{1}{18\sqrt{3}})|s|)$, and
$(x+(\frac{\sqrt{3}}{4}+\frac{1}{36})|s|,y+(\frac{1}{4}+\frac{1}{36\sqrt{3}})|s|)$,
respectively. Each of these balls have radius $|s|$.

Figure 4: (a) Three balls cover $T\oplus B_{0}$ (notice that in actual
construction, $T$ is much smaller compare to the balls.) (b) The red line
shows the border of $B$. The blue line shows the border of the bottom one-
third sector of $T\oplus B_{0}$.

Let the bottom-left corner of $T$ be $c_{l}$, let $a$ be the point on the
border of $T\oplus B_{0}$ such that $a$ is on the line extended from
$(\text{center}(T),c_{l})$. Due to construction, $\text{dist}(c_{l},a)=|s|$.
We will prove that $T\oplus B_{0}\subseteq A\cup B\cup C$ by showing that $B$
covers the bottom one-third sector of $T\oplus B_{0}$. For now, we will focus
on the bottom one-third sector of $T\oplus B_{0}$, see Figure 4(b).

Let $c_{m}$ be the middle point of the bottom side of $T$. We focus on the
points on $(c_{l},c_{m})$, and their nearest points on the border of $T\oplus
B_{0}$. Let $c\subseteq(c_{l},c_{m})$, and let $c_{T}$ be the nearest point of
$c$ on the border of $T\oplus B_{0}$. Let $c_{B}$ be the point on the border
of $B$ such that $c_{B}$ lies on the line extended from $(c,c_{T})$. We show
that $B$ covers half of the one-third sector by showing that
$\text{dist}(c_{T},c_{B})>0$.

Notice that $\text{intersection}(A,B)$ is guaranteed to lie on the line
extended from $(c_{l},a)$ since
$\text{dist}(\text{center}(B),\text{center}(T))=\text{dist}(\text{center}(A),\text{center}(T))$.

$\displaystyle\measuredangle(a,\text{center}(T),\text{center}(B))=cos^{-1}(\frac{\frac{1}{2}+\frac{1}{18\sqrt{3}}}{1+\frac{1}{9\sqrt{3}}})=\frac{\pi}{3}$
$\displaystyle\measuredangle(\text{center}(T),a,\text{center}(B))=sin^{-1}(\frac{\frac{1}{2}+\frac{1}{18\sqrt{3}}}{1+\frac{1}{9\sqrt{3}}})=\frac{\pi}{6}$
$\displaystyle\measuredangle(a,\text{center}(B),\text{center}(T))$
$\displaystyle=\pi-\measuredangle(a,\text{center}(B),\text{center}(T))-\measuredangle(\text{center}(T),a,\text{center}(B))=\frac{\pi}{2}$

Then we can calculate $\text{dist}(a,\text{center}(B))$:

$\displaystyle\text{dist}(a,\text{center}(B))=cos(\frac{\pi}{6})\cdot(1+\frac{1}{9\sqrt{3}})|s|\approx
0.922|s|<|s|$

We have $\text{dist}(c,a)\geq\text{dist}(c,\text{intersection}(A,B))$ because
$\text{dist}(a,\text{center}(B))<\text{radius}(B)$, and since
$\text{dist}(\text{intersection}(A,B),\text{center}(B))=|s|$, we know that
$\text{intersection}(A,B)$ lies below and to the left of $a$. Therefore
$\text{dist}(a,\text{intersection}(A,B))>0$.

Let $c\subseteq(c,c_{m})$. We focus on the triangle created by $c$, $c_{T}$
and $\text{center}(B)$. As we slide $c_{T}$ along the border of $T\oplus
B_{0}$ towards its bottom, $\text{dist}(\text{center}(B),c_{T})$ decreases
which means
$\text{dist}(\text{center}(B),c_{T})<0.922|s|<|s|=\text{dist}(\text{center}(B),c_{B})$.
Therefore $\text{dist}(c_{T},c_{B})>0$ for $c\subseteq(c_{l},c_{m})$. Let
$c_{r}$ be the bottom-right corner of $T$, we can arrive at the same
conclusion for $c\subseteq(c_{m},c_{r})$. Therefore $B$ covers the bottom one-
third sector of $T\oplus B_{0}$.

Using a similar argument, we can prove that the $A$ and $C$ cover the top-
left, and top-right one-third sectors of $T\oplus B_{0}$, respectively.
Therefore $T\oplus B_{0}\subseteq A\cup B\cup C$, which completes the proof of
the lemma.

This proves that any optimal ball intersecting $s$ can be covered by three of
the balls in $\mathcal{B}_{s}$. Using Algorithm 1, but replacing the square
grid with the sheared triangular grid described in this section, we obtain the
following theorem.

######  Theorem 2.8.

A $3$-approximation of the $\lambda$-low-density value of a set $S$ of $n$
segments in the plane can be computed in $O(n^{2})$ time.

##  3 Improving the running time

The bottleneck of of Algorithm 1 is step 3, which for each segment $s\in S$
constructs the set $S^{\prime}\subseteq S$ containing all the segments in $S$
longer than $s$ and intersecting $Q_{s}$. For each segment this takes linear
time. However, from Corollary 2.4, we know that $S^{\prime}$ only contains
$O(\lambda)$ segments and we also know the regions $Q_{s}$ for all segments
$s\in S$ at the start of the algorithm. We will utilise both these
observations to speed up Step 3 of the algorithm by modifying a compressed
quadtree [10]. We start by introducing some preliminaries, and prove a key
lemma that will allow us to store the segments in a compressed quadtree.

###  3.1 Preliminaries

Scale and translate the input such that all endpoints of the segments are
contained in the unit square $[0,1]\times[0,1]$.

During the construction process of the quadtree, we continuously divide each
square into four equal-sized squares. Each cell is also a node in the
quadtree. The $x$ and $y$-coordinates of the corners of these cells have the
form $k/2^{i}$, where $i$ and $k$ are integers. In a grid $G_{r}$, a grid cell
has side length $r$, see Figure 5.

Figure 5: The grid described by the squares of size $1/2^{i}$ is denoted
$G_{1/2^{i}}$. (a) Showing $G_{1/2}$, and (b) $G_{1/4}$.

In the quadtree construction, the root of the quadtree is always the unit
square. We say a square $\square$ is a canonical square if and only if
$\square$ is a square in the constructed quadtree.

With unit square and canonical square defined, we will next show that there
exists a constant number of canonical squares that cover $Q_{s}$. These
canonical squares can then be used to construct a quadtree to store our
segments.

In order to cover $Q_{s}$ with canonical squares, we first need to define the
_most significant separator_ of $Q_{s}$. Consider the vertical line at
$x=\frac{k}{2^{i}}$, $i,k\in\mathbb{Z}$, where $k$ is odd. We say that it is a
vertical separator of $Q_{s}$ if it intersects $Q_{s}$. We say
$x=\frac{k}{2^{i}}$ is more significant than $x=\frac{k^{\prime}}{2^{j}}$ if
$i<j$. We define a horizontal separator symmetrically. Notice that each
$Q_{s}$ can intersect exactly one most significant vertical and one most
significant horizontal separator. Indeed, if $Q_{s}$ intersects two most
significant vertical separators $x=\frac{k}{2^{i}}$ and
$x=\frac{k^{\prime}}{2^{i}}$, $k\neq k^{\prime}$, there exits some
$k^{\prime\prime}\in(k,k^{\prime})$ such that $k^{\prime\prime}$ is even,
since both $k$ and $k^{\prime}$ are odd. Then $Q_{s}$ also intersects
$x=\frac{k^{\prime\prime}}{2^{i}}=\frac{k^{\prime\prime}/2}{2^{i+1}}$, which
means $x=\frac{k}{2^{i}}$ cannot be the most significant separator.

The proof of the following lemma can be found in Appendix A.

######  Lemma 3.1.

For all $s\in S$, we can construct $O(1)$ canonical squares to cover $Q_{s}$
such that the side length of each canonical square is at most $\left\lvert
s\right\rvert$.

In the proof of Lemma 3.1 we used a constructive proof to show how to cover
$Q_{s}$ with canonical squares. However, to compute the canonical squares
efficiently, we need to find the most significant separator of $Q_{s}$ fast.
Next we show that computing the most significant separator can be done in
constant time, assuming the unit RAM model.

######  Lemma 3.2.

Finding the most significant separators of $Q_{s}$ takes $O(1)$ time under the
unit RAM model.

######  Proof 3.3.

We use the bit twiddling method in [10]. We assume that $\alpha,\beta\in[0,1)$
are written in base two as $\alpha=0.\alpha_{1}\alpha_{2}$…, and
$\beta=0.\beta_{1}\beta_{2}$… Let $\text{bit}_{\triangle}(\alpha,\beta)$ be
the index of the first bit after the period in which they differ.

Let $\alpha,\beta$ be the $x$-coordinate of the top-left and top-right corner
of $Q_{s}$, respectively. Let $i=\text{bit}_{\triangle}(\alpha,\beta)$. Notice
that if the first $i-1$ bits of $\alpha$ and $\beta$ are the same, they must
reside in a canonical square which is a cell of $G_{1/2^{i-1}}$. For example,
if $\alpha_{1}=\beta_{1}=1$, then $\alpha,\beta\in[1/2,1)$. Furthermore, if
$\alpha_{2}=\beta_{2}=0$, then $\alpha,\beta\in[2/4,3/4)$. Therefore, the most
significant vertical separator must be either $x=\alpha$, $x=\beta$ or the
immediate next separator to the right side of $\alpha$ which takes the form
$x=k/2^{i}$, where $k$ is odd.

We can then find the most significant separator by adding $1/2^{i}$ to
$\alpha$, and set the bits after $i$th bit to $0$. Let
$l=0.\alpha_{1}\alpha_{2}...\alpha_{2^{i-1}}1$. We report the more significant
separator among $\alpha$, $\beta$, and $l$ as the most significant vertical
separator of $Q_{s}$. And since it takes $O(1)$ time to calculate
$\text{bit}_{\triangle}(\alpha,\beta)$, calculating $l$ and comparing $l$,
$\alpha$, and $\beta$ also takes $O(1)$ time.

Har-Peled [10] justified why it is reasonable to assume that
$\text{bit}_{\triangle}(\cdot,\cdot)$ can be computed in constant time. Modern
float number is represented by exponent and mantissa. If two numbers have
different exponents, then we can compute $\text{bit}_{\triangle}(\cdot,\cdot)$
by giving the larger component. Otherwise, we can XOR the mantissas, and
$\log_{2}(\cdot)$ the result. Har-Peled [10] also noted that these are built-
in operations on some CPU models. Therefore assuming that
$\text{bit}_{\triangle}(\cdot,\cdot)$ requires constant time to compute is a
reasonable assumption.

###  3.2 Preprocessing: Generate canonical squares

Above we proved that we can generate a set $\mathcal{C}_{s}$ of canonical
squares of size at most $|s|$ that cover $Q_{s}$. Given a set $S$ of segments
and the set $\mathcal{C}_{s}$ for each segment $s$ in $S$, we call $s$ the
associated segment of the squares in $\mathcal{C}_{s}$, and we call the
squares in $\mathcal{C}_{s}$ the associated squares of $s$. We perform the
following steps:

  1. 1.

For each segments $s$, perform a linear scan of the canonical squares in
$\mathcal{C}_{s}$ and mark the squares that intersect $s$. We call $s$ the
intersecting segment of these squares, and we call these squares the
intersecting squares of $s$.

  2. 2.

Let $\mathcal{C}=\cup_{s\in S}\mathcal{C}_{s}$ and sort all the canonical
squares in $\mathcal{C}$ based on their sizes, then by coordinates of the
bottom-left corners, and, finally, by the length of the segment they intersect
in decreasing order.

  3. 3.

To remove duplicate squares in $\mathcal{C}$, perform a linear scan of the
sorted squares in the list, merge adjacent squares if they are identical.
While merging two squares, also merge the set of segments they associate with
and the set of segments they intersect. The segments that intersect the same
square are ordered in decreasing order of length.

At the end of the preprocessing step, we have $O(n)$ canonical squares
according to Lemma 3.1. Each segment keeps a list of pointers to its canonical
squares, and each canonical square holds the segment(s) it is associated with,
and the segment(s) it intersects in decreasing order of length. Let
$Q_{s}^{\prime}$ be the region covered by the set of canonical squares in
$\mathcal{C}_{s}$. We can now summarise the preprocessing step.

######  Lemma 3.4.

The preprocessing step generates $O(n)$ canonical squares, where each
canonical square stores pointers to the segments intersecting it, in
decreasing order of length, and its associated segments. The preprocessing
step takes $O(n\log n)$ time.

######  Proof 3.5.

Scaling and translating segments within the unit square takes $O(n)$ time.
Then for each segment $s$, cover $Q_{s}$ in $O(1)$ time by using the method
described in the proofs of Lemmas 3.1 and 3.2. In Lemma 3.1, we showed that
each $Q_{s}$ generates a constant number of canonical squares, therefore this
step takes $O(n)$ time, and generates $O(n)$ canonical squares. Removing
duplicates requires a sorting step, which takes $O(n\log n)$ time.

###  3.3 An efficient construction using compressed quadtrees

We will construct the compressed quadtree from the $O(n)$ canonical squares
constructed in the previous section. Let $\square_{v}$ denote the square
associated with node $v$. We say a segment $s$ intersects a node $v$ in the
compressed quadtree if $s$ intersects $\square_{v}$. We use the below lemma
from [10].

######  Lemma 3.6 (Lemma 2.11 in [10]).

Given a list $\mathcal{C}$ of $n$ canonical squares, all lying inside the unit
square, one can construct a (minimal) compressed quadtree $\mathcal{T}$ such
that for any square $c\in C$, there exists a node $v\in\mathcal{T}$, such that
$\square_{v}=c$. The construction time is $O(n\log n)$.

We now apply Lemma 3.6, with the $O(n)$ canonical squares constructed in
Section 3.2 as input, we obtain a compressed quadtree, where each canonical
square corresponds to an internal node.

Once we complete the construction of the compressed quadtree $\mathcal{T}$, we
start the _push-down step_ as follows. Sort the segments in increasing order
of length, then iterate through the segments. For each segment $s\in S$, go to
the internal nodes in $\mathcal{T}$ that it intersects with. Search all of
their children to check if $s$ intersects with them. If $s$ does, insert $s$
at the beginning of the list of intersecting segments of that internal node
and continue the search in its children.

Using a naive analysis, since the compressed quadtree has at most $n$ nodes,
applying the push-down step for all $n$ segments takes $O(n^{2})$ time in
total. However, below we will show that the running time improves when the
analysis is done in terms of the $\lambda$-low-density value of $S$ as well as
$n$.

First note that the arguments for Corollary 2.4 can easily be extended to
prove the following corollary.

######  Corollary 3.7.

Let $S$ be a set of $\lambda$-low-density segments in $\mathbb{R}^{2}$. For
any $s\in S$, let $Q$ be a $a\left\lvert s\right\rvert\times b\left\lvert
s\right\rvert$ rectangle such that $a$ and $b$ are constants, and
$P_{s}\subseteq Q$. The number of segments $s^{\prime}\in S$ with $\left\lvert
s^{\prime}\right\rvert\geq\left\lvert s\right\rvert$ that intersect $Q$ is
$O(\lambda)$.

The corollary implies that only $O(\lambda)$ segments intersects the canonical
squares covering $Q_{s}$. Using this result we can now improve the running
time.

######  Lemma 3.8.

The compressed quadtree takes $O(n\log n+\lambda n)$ time to construct. The
push-down step takes $O(\lambda n)$, and the resulting data structure uses
$O(\lambda n)$ space.

######  Proof 3.9.

According to Lemma 3.4 and Lemma 3.6, one can construct a compressed quadtree
with $O(n)$ squares in $O(n\log n)$ time that contains the $O(n)$ required
canonical squares. It remains only to analyse the running time of the push-
down step.

Sorting the segments takes $O(n\log n)$ time. Recall that in Corollary 2.4, we
showed that for any $s\in S$, the number of segments that are longer than or
equal to the length of $s$ that intersect with $Q_{s}$ is $O(\lambda)$. The
same holds for $Q_{s}^{\prime}$. Notice that in the push-down step, for each
associated internal node $v$ of a segment $s$, one only add $s$ to the
descendants of $v$ if they intersect $s$. The side lengths of associated
canonical squares of a segment have to be less than or equal to the length of
that segment. Therefore, $s$ is only added to the internal nodes whose
associated segments are shorter than or equals to $s$. In another word, an
internal node $v$ adds $s$ as intersecting segment if and only if $\left\lvert
s\right\rvert$ is greater than or equal to the length of the associated
segment of $v$. As a result each internal node adds at most $\lambda$
segments. And since each $Q_{s}^{\prime}$ is covered by a constant number of
squares, we add $O(\lambda)$ segments to each $Q_{s}^{\prime}$. The push-down
step takes $O(\lambda n)$ time. The overall time complexity is $O(n\log
n+\lambda n$).

We have a constant number of associated squares for each segment. Since each
square results in at most one internal nodes and four children, we have a
compressed quadtree with $O(n)$ nodes. In addition, each internal node
associated with each $Q_{s}^{\prime}$ stores $O(\lambda)$ intersecting
segments. Therefore we stored $O(\lambda n)$ intersecting segments and the
compressed quadtree uses $O(\lambda n)$ space in total.

###  3.4 The final approximation algorithm

Given the $3$-approximation algorithm in Section 2.2 together with the
compressed quadtree introduced in Section 3.3, we are now ready to present the
final algorithm. In Algorithm 2, we query the compressed quadtree described in
the previous section to get our $3$-approximation. Recall that
$Q_{s}^{\prime}$ is the region covered by the set of canonical squares we
generated from $Q_{s}$ in the preprocessing step. Similarly to what we have
done in Section 2.2, we will use a set of triangles to cover $Q_{s}^{\prime}$,
and we will cover each triangle with three balls. We denote the set of balls
that cover $Q_{s}^{\prime}$ by $\mathcal{B}_{s}^{\prime}$.

Algorithm 2 A faster 3-approximation using quadtrees

1:$S$: a set of segments in $\mathbb{R}^{2}$

2:$\mathcal{T}\leftarrow$ a compressed quadtree storing $S$ (as described in
Section 3.3.)

3:$\lambda\leftarrow 0$

4:for each $s$ in $S$ do

5: $S^{\prime}\leftarrow$ intersecting segments of the associated nodes of $s$
of length at least $|s|$

6: $\mathcal{B}_{s}^{\prime}\leftarrow$ the set of balls of radius
$\left\lvert s\right\rvert$ that cover $Q_{s}^{\prime}$.

7: for each
$\mathord{\mathchoice{\leavevmode\resizebox{}{6.75pt}{\leavevmode\hbox{\set@color\raisebox{0.0pt}{$\displaystyle\bigcirc$}}}}{\leavevmode\resizebox{}{6.75pt}{\leavevmode\hbox{\set@color\raisebox{0.0pt}{$\textstyle\bigcirc$}}}}{\leavevmode\resizebox{}{4.72499pt}{\leavevmode\hbox{\set<EMAIL_ADDRESS>in $\mathcal{B}_{s}^{\prime}$ do

8: $\lambda$ = max($\lambda$, number of segments in $S^{\prime}$ that
intersect
$\mathord{\mathchoice{\leavevmode\resizebox{}{6.75pt}{\leavevmode\hbox{\set@color\raisebox{0.0pt}{$\displaystyle\bigcirc$}}}}{\leavevmode\resizebox{}{6.75pt}{\leavevmode\hbox{\set@color\raisebox{0.0pt}{$\textstyle\bigcirc$}}}}{\leavevmode\resizebox{}{4.72499pt}{\leavevmode\hbox{\set<EMAIL_ADDRESS>
9:return $\lambda$

######  Theorem 3.10.

Given a set $S$ of segments in $\mathbb{R}^{2}$, one can compute a
$3$-approximation of the density value of $S$ in $O(n\log n+\lambda n)$ time.

######  Proof 3.11.

Iterate through all the segments, and one of them must be the shortest segment
$s$ that intersects an optimal ball. According to Lemma 3.1, the union of the
associated squares of $s$ covers $Q_{s}$, and each associated square has side
length less than or equals to $\left\lvert s\right\rvert$. In Section 2.2 it
was shown that one can use a constant number of equilateral triangles of side
length $\left\lvert s\right\rvert/9$ to cover a $Q_{s}$, therefore the same
can be done to each $Q_{s}^{\prime}$. In Lemma 2.6, we have shown that there
exists three balls in $\mathcal{B}_{s}$ of radius $\left\lvert s\right\rvert$
that cover any optimal ball centered anywhere in each of the triangles.
Therefore our algorithm generates a constant number of balls that cover
$Q_{s}^{\prime}$, the region covered by the associated squares of $s$, and the
ball that intersects maximum number of segments intersects at most $\lambda/3$
segments.

We have shown in Lemma 3.8 that building a quadtree with $n$ segments takes
$O(n\log n+\lambda n)$ time. For each segment, one can generate $O(1)$
canonical squares (Lemma 3.1), therefore there are $O(1)$ associated nodes for
each segment $s$. We build the quadtree during the construction so that the
intersecting segments of duplicated canonical squares are sorted in decreasing
order of length. Notice that during the push-down step, we preserve this order
by pushing down the shorter segments first, then the longer ones. Due to
Corollary 3.7, the number of segments with lengths longer than or equals to
$\left\lvert s\right\rvert$ that intersect $Q_{s}^{\prime}$ is $O(\lambda)$,
hence, it takes $O(\lambda)$ time to retrieve the segments $S^{\prime}$ in $S$
that intersects with $Q_{s}^{\prime}$, and since we generates a constant
number of balls, it takes $O(\lambda)$ time to find the ball that intersects
the most number of segments. Summing up over all the $n$ segments the final
running time of this step is $O(\lambda n+n\log n)$.

The time complexity of this algorithm is dominated by the construction of the
compressed quadtree, which is $O(n\log n+\lambda n)$.

This completes the main result of the paper. In the appendix we show how one
can modify the construction of the quadtree using a $\mathcal{Z}$-order of the
canonical squares, as proposed by Har-Peled [10]. This gives the following
theorem:

######  Theorem 3.12.

One can maintain a $3$-approximation of the density value of set of segments
in $O(\log n+\lambda^{2}$) amortized time per insertion.

##  4 Experiments

We implemented a simple algorithm to obtain the $4$-approximate density values
on several trajectory data sets. The algorithm is a simplification of the
3-approximation algorithm presented in Section 2.2.

The data sets were provided to us by the authors of [9]. Each data set
contains a number of trajectories. Table 1 summarises the data sets, and its
information is taken from [9]. This experiment aims to show the practicality
of our approximation method and motivate the study of low density.

Table 1: Real data sets containing trajectories in $\mathbb{R}^{2}$, showing number of input trajectories $n$, average number of vertices per trajectory, and a description Data set | $n$ | #Vertices | Trajectory Description
---|---|---|---
Vessel-M [12] | 106 | 23.0 | MS River USA shipping vessels Shipboard AIS.
Vessel-Y [12] | 187 | 155.2 | Yangtze River shipping vessels Shipboard AIS.
Truck [6] | 276 | 406.5 | GPS of 50 concrete trucks in Athens, Greece.
Bus [6] | 148 | 446.6 | GPS of School buses.
Taxi [19, 20] | 180,736 | 75.7 | Beijing taxi trajectories split into trips.
Geolife [23, 21, 22] | 18,670 | 1,332.5 | People movement, mostly in Beijing, China.
Pigeon [7] | 131 | 970.0 | Homing Pigeons (release sites to home site).
Seabird [13] | 134 | 3,175.8 | GPS of Masked Boobies in Gulf of Mexico.
Cats [11] | 154 | 526.1 | Pet house cats GPS in RDU, NC, USA.
Buffalo [3] | 165 | 161.3 | Radio-collared Kruger Buffalo, South Africa.
Gulls [18] | 253 | 602.1 | Black-backed gulls GPS (Finland to Africa).
Bats [8] | 545 | 127.2 | Video-grammetry of Daubenton trawling bats.

We used the 4-approximation algorithm to estimate the density values of the
trajectories in each data set. We record the total number of curves, the
maximum curve size, the max, and median estimate density values, and the
median density to curve size ratio for each data set. We summarise the
information in Table 2. Additional information and experiments can be found in
Appendix C.

Table 2: The table lists $4$-approximate density values of $12$ data sets. The second and third columns show the number of curves and the maximum curve size. The following two columns shows the maximum and median density value. The last column shows the median ratio between $\lambda$ and the size of the curve $n$.  Data set | #Curves | MaxCurveSize | Max | Median | Median $\lambda/n$
---|---|---|---|---|---
Vessel-M | 102 | 142 | 17 | 2.0 | 0.133
Vessel-Y | 186 | 559 | 3 | 3.0 | 0.020
Truck | 272 | 991 | 45 | 11.0 | 0.028
Bus | 144 | 1015 | 17 | 7.0 | 0.016
Taxi | 947 | 3340 | 682 | 14 | 0.091
GeoLife | 999 | 64482 | 335 | 5 | 0.011
Pigeon | 130 | 1645 | 665 | 28.0 | 0.038
Seabird | 133 | 8556 | 1483 | 351 | 0.131
Cat | 153 | 11122 | 411 | 45 | 0.224
Buffalo | 162 | 479 | 82 | 21.0 | 0.169
Gull | 126 | 16019 | 1520 | 50.5 | 0.159
Bat | 544 | 735 | 8 | 2.0 | 0.020

In the experiment, we estimated the density values of trajectories in twelve
real-world data sets. Our observation is that most of the data sets’ estimated
density values are low. In eleven data sets (all except Seabird), the median
estimate density values are less than $51$. In six data sets, Vessel-Y, Truck,
Bus, GeoLife, Pigeon, and Bat, the median $\lambda/n$ ratios are less than
$0.04$, where $\lambda$ and $n$ are the estimated density value and the size
of the curve. Although the density values are estimates, the notion of low
density for trajectories is valuable. The algorithms that perform better when
the density value is small, e.g. the algorithm by Driemel et al. [5], can be
applied to these data sets to improve efficiency.

##  5 Concluding remarks

In this paper we considered the problem of approximating the $\lambda$-density
value of a set of segments. Our main results is a $3$-approximation algorithm
running in $O(n\log n+\lambda n)$ time, where $\lambda$ is the density value.
Previously, only an $O(n\log^{3}n+\lambda n\log^{2}n+\lambda^{2}n)$ time
algorithms was known for the special case when the segments are disjoint. Our
approach can be extended to handle insertions, where each insert operation can
be done in $O(\log n+\lambda^{2})$ amortized time.

We also implemented a simple $4$-approximation algorithm to estimate the
density values of twelve real-world trajectory data sets. We observed that the
estimated densities for most of the data sets are small constants. We also
observed that the trajectories in half of the data sets have low density-to-
size ratios, which indicates that low density is a practical, realistic input
model for trajectories.

## References

  * [1] K. Bringmann.  Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails.  In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 661–670. IEEE Computer Society, 2014.  doi:10.1109/FOCS.2014.76.
  * [2] Daniel Chen, Anne Driemel, Leonidas J. Guibas, Andy Nguyen, and Carola Wenk.  Approximate map matching with respect to the Fréchet distance.  In Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 75–83. Society for Industrial and Applied Mathematics, 2011.  doi:10.1137/1.9781611972917.8.
  * [3] Paul Cross, Dennis Heisey, Justin Bowers, Craig Hay, J. Wolhuter, Peter Buss, M. Hofmeyr, Anita Michel, Roy Bengis, Tania Bird, Johan du Toit, and Wayne Getz.  Disease, predation and demography: Assessing the impacts of bovine tuberculosis on african buffalo by monitoring at individual and population levels.  Journal of Applied Ecology, 46:467–475, 12 2008.  doi:10.1111/j.1365-2664.2008.01589.x.
  * [4] Mark de Berg, A. Frank Van der Stappen, Jules Vleugels, and Matthew Katz.  Realistic input models for geometric algorithms.  Algorithmica, 34:81–97, 2002.  doi:10.1007/s00453-002-0961-x.
  * [5] Anne Driemel, Sariel Har-Peled, and Carola Wenk.  Approximating the Fréchet distance for realistic curves in near linear time.  Discrete Computational Geometry, 48(1):94–127, 2012.  doi:10.1007/s00454-012-9402-z.
  * [6] Elias Frentzos, Kostas Gratsias, Nikos Pelekis, and Yannis Theodoridis.  Nearest neighbor search on moving object trajectories.  In Proceedings of the 9th International Symposium on Advances in Spatial and Temporal Databases (SSTD), volume 3633 of Lecture Notes in Computer Science, pages 328–345. Springer, 2005.  doi:10.1007/11535331_19.
  * [7] Anna Gagliardo, Enrica Pollonara, and Martin Wikelski.  Pigeon navigation: exposure to environmental odours prior release is sufficient for homeward orientation, but not for homing.  The Journal of Experimental Biology, 219:2475–2480, 2016.  doi:10.1242/jeb.140889.
  * [8] Luca Giuggioli, Thomas McKetterick, and Marc Holderied.  Delayed response and biosonar perception explain movement coordination in trawling bats.  PLoS Computational Biology, 11(3):1–21, 2015.  doi:10.1371/journal.pcbi.1004089.
  * [9] Joachim Gudmundsson, Michael Horton, John Pfeifer, and Martin P. Seybold.  A practical index structure supporting Fréchet proximity queries among trajectories.  ACM Trans. Spatial Algorithms Syst., 7(3), 2021.  doi:10.1145/3460121.
  * [10] Sariel Har-Peled.  Geometric approximation algorithms.  American Mathematical Society, 2011.
  * [11] Roland Kays, James Flowers, and Suzanne Kennedy-Stoskopf.  Cat tracker project.  2016\.  URL: http://www.movebank.org/.
  * [12] Huanhuan Li, Jingxian Liu, Wen Liu, Naixue Xiong, Kefeng Wu, and Tai-Hoon Kim.  A dimensionality reduction-based multi-step clustering method for robust vessel trajectory analysis.  Sensors, 17(8):1792, 2017.  doi:10.3390/s17081792.
  * [13] Caroline Poli, Autumn-Lynn Harrison, Adriana Vallarino, Patrick Gerard, and Patrick Jodice.  Dynamic oceanography determines fine scale foraging behavior of Masked Boobies in the Gulf of Mexico.  PLoS ONE, 12(6):1–24, 2017.  doi:10.1371/journal.pone.0178318.
  * [14] Otfried Schwarzkopf and Jules Vleugels.  Range searching in low-density environments.  Information Processing Letters, 60(3):121–127, 1996.  doi:10.1016/S0020-0190(96)00154-8.
  * [15] A. Frank Van der Stappen.  Motion planning amidst fat obstacles.  PhD thesis, Utrecht University, 1994.
  * [16] A. Frank van der Stappen, Dan Halperin, and Mark H. Overmars.  The complexity of the free space for a robot moving amidst fat obstacles.  Computational Geometry, 3(6):353–373, 1993.  doi:10.1016/0925-7721(93)90007-S.
  * [17] Ron Wein.  Exact and efficient construction of planar Minkowski sums using the convolution method.  In Proceedings of the 14th Conference on Annual European Symposium on Algorithms (ESA), volume 4168 of Lecture Notes in Computer Science, pages 829––840. Springer-Verlag, 2006.  doi:10.1007/11841036_73.
  * [18] Martin Wikelski, Elena Arriero, Anna Gagliardo, Richard Holland, Markku Huttunen, Risto Juvaste, Inge Müller, G.M. Tertitski, Kasper Thorup, John Wild, Markku Alanko, Franz Bairlein, Alexander Cherenkov, Alison Cameron, Reinhard Flatz, Juhani Hannila, Ommo Hüppop, Markku Kangasniemi, Bart Kranstauber, and Ralf Wistbacka.  True navigation in migrating Gulls requires intact olfactory nerves.  Scientific Reports, 5:17061, 2015.  doi:10.1038/srep17061.
  * [19] Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun.  Driving with knowledge from the physical world.  In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 316–324. Association for Computing Machinery, 2011.  doi:10.1145/2020408.2020462.
  * [20] Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang.  T-drive: Driving directions based on taxi trajectories.  In Proceedings of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, pages 99–108, 2010\.  doi:10.1145/1869790.1869807.
  * [21] Yu Zheng, Quannan Li, Yukun Chen, Xing Xie, and Wei-Ying Ma.  Understanding mobility based on gps data.  In Proceedings of the 10th International Conference on Ubiquitous Computing (UbiComp), pages 312–321. Association for Computing Machinery, 2008.  doi:10.1145/1409635.1409677.
  * [22] Yu Zheng, Xing Xie, and Wei-Ying Ma.  Geolife: A collaborative social networking service among user, location and trajectory.  IEEE Data(base) Engineering Bulletin, 33:32–39, 2010.
  * [23] Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma.  Mining interesting locations and travel sequences from GPS trajectories.  In Proceedings of the 18th International Conference on World Wide Web (WWW), pages 791––800. Association for Computing Machinery, 2009\.  doi:10.1145/1526709.1526816.

##  Appendix A Proof of Lemma 3.1

######  Lemma 3.1.

For all $s\in S$, we can construct $O(1)$ canonical squares to cover $Q_{s}$
such that the side length of each canonical square is at most $\left\lvert
s\right\rvert$.

Figure 6: (a) Expanding $Q_{s}$ into $Q_{s}^{\prime}$ so it can be split up
into canonical squares. We say $x=\frac{1}{2}$ is a more significant separator
than $x=\frac{1}{4}$. (b) Expanding the top-right part of $Q_{s}$ into $B$,
whose side is twice as long as the side of $A$.

######  Proof A.1.

If $Q_{s}$ is identical to a canonical square then we are trivially done. If
not, for an arbitrary $Q_{s}$, let $x=\frac{k}{2^{i}}$ and
$y=\frac{k^{\prime}}{2^{j}}$ be the most significant vertical and horizontal
separators, respectively. They intersect at
$(\frac{k}{2^{i}},\frac{k^{\prime}}{2^{j}})$, and separate $Q_{s}$ into four
parts (see Figure 6(b)). Without loss of generality, let top-right part be the
largest part. Let $(a,b)$ be the top-right corner of $Q_{s}$, and let
$c=-\lceil\log_{2}(\text{max}(\left\lvert
a-\frac{k}{2^{i}}\right\rvert,\left\lvert
b-\frac{k^{\prime}}{2^{j}}\right\rvert)\rceil$.

We expand the top-right part of $Q_{s}$ to a square $B$ which has
$(\frac{k}{2^{i}},\frac{k^{\prime}}{2^{j}})$ as bottom-left corner, and
$(\frac{k}{2^{i}}+\frac{1}{2^{c}},\frac{k^{\prime}}{2^{j}}+\frac{1}{2^{c}})$
as top-right corner (non-inclusive). Notice that $c>i,j$, because the opposite
suggests that $Q_{s}$ intersects a more significant vertical separator than
$x$ or a more significant horizontal separator than $y$. Therefore $B$ is the
intersection of the following halfplanes.

$\displaystyle x$
$\displaystyle\geq\frac{k}{2^{i}}=\frac{1}{2^{c}}\cdot\frac{k}{2^{i-c}}$
$\displaystyle y$
$\displaystyle\geq\frac{k^{\prime}}{2^{j}}=\frac{1}{2^{c}}\cdot\frac{k^{\prime}}{2^{j-c}}$
$\displaystyle x$
$\displaystyle<\frac{k}{2^{i}}+\frac{1}{2^{c}}=\frac{1}{2^{c}}\cdot(\frac{k}{2^{i-c}}+1)$
$\displaystyle y$
$\displaystyle<\frac{k^{\prime}}{2^{j}}+\frac{1}{2^{c}}=\frac{1}{2^{c}}\cdot(\frac{k^{\prime}}{2^{j-c}}+1)$

Since $c>i,j$, and $c,i,j,k,k^{\prime}\in\mathbb{Z}$, both $\frac{k}{2^{i-c}}$
and $\frac{k^{\prime}}{2^{j-c}}$ are integers, which means $B$ satisfies the
definition of a cell in $G_{1/2^{c}}$. And since $B$ is contained inside the
unit square, $B$ is a canonical square.

We now show that $B$ can be split into a constant number of canonical squares
with side lengths less than or equal to $\left\lvert s\right\rvert$. Let
$d=-\lfloor\log_{2}(\text{max}(\left\lvert
a-\frac{k}{2^{i}}\right\rvert,\left\lvert
b-\frac{k^{\prime}}{2^{j}}\right\rvert)\rfloor$. Let $A$ be the square with
$(\frac{k}{2^{i}},\frac{k^{\prime}}{2^{j}})$ as its bottom-left corner, and
$(\frac{k}{2^{i}}+\frac{1}{2^{d}},\frac{k^{\prime}}{2^{j}}+\frac{1}{2^{d}})$
as its top-right corner. $Q_{s}$ has to be bigger than $A$ as the opposite
suggests $A=B$. Therefore we assume $Q_{s}$ is bigger than $A$. The side
length of $B$ is less than two times the side length of $Q_{s}$, assuming that
the area of the other three parts of $Q_{s}$ is minimal. Therefore the side
length of $B$ is less than $10\left\lvert s\right\rvert$. Notice that dividing
a canonical square evenly into four squares also gives canonical squares.
Therefore we can divide $B$ into canonical squares. Since the side length of
$B$ is less than $10\left\lvert s\right\rvert$, it takes at most
$\lceil\log_{2}(10)\rceil=4$ splits before the resulting canonical squares
have side lengths less than $\left\lvert s\right\rvert$. We can expand the
rest of the quadrants to the same size as $B$, and split them using the same
method.

The above argument applies to the scenario where $Q_{s}^{\prime}=Q_{s}$ is
already a canonical square. A constant number of splits for each of four parts
of $Q_{s}^{\prime}$ leads to a constant number of canonical squares. The proof
is complete.

##  Appendix B Make the compressed quadtrees dynamic

A natural follow-up question of the preceding section is whether our
compressed quadtree can be made dynamic. Insert and delete operations are
helpful as they allow dynamic input.

Har-Peled [10] defined an ordering of points and canonical squares, which we
will call the $\mathcal{Z}$-order. As in previous sections, we are only
interested in storing canonical squares. Therefore we only give an overview of
the definition of $\mathcal{Z}$-order for canonical squares.

First, imagine we have a quadtree, and we traverse this quadtree with the DFS
traversal (see Figure 7). And on each root of a subtree, we always traverse
its children in a set order. We always visit the bottom-left child first, then
the bottom-right child, top-left child, and top-right child. Then the DFS
traversal defines a total ordering of the canonical squares. We say
$\square\prec\widehat{\square}$ if we visit $\square$ before we visit
$\widehat{\square}$ using the above DFS traversal.

Figure 7: The $\mathcal{Z}$-order. Right canonical squares are the children of
left canonical square.

With the $\mathcal{Z}$-order defined, we can store the canonical squares in a
balanced binary search data structure such as a skip list or an AVL tree.
However, we need to be able to resolve the $\mathcal{Z}$-order of two
canonical squares in $O(1)$ time.

Observe that in a quadtree, distinct canonical squares have distinct centers,
and $\text{center}(\square)$ lies in $\widehat{\square}$ if and only if
$\square\subseteq\widehat{\square}$. Furthermore, if
$\square\subseteq\widehat{\square}$, then $\widehat{\square}\prec\square$, and
if $\widehat{\square}\subseteq\square$, then $\square\prec\widehat{\square}$.
Therefore we can decide if one square is the ancestor of another, and if so,
resolve the $\mathcal{Z}$-order of two canonical squares in $O(1)$ time.

Otherwise, we need to find the smallest canonical square that contains both
$\square$ and $\widehat{\square}$ by using
$\text{bit}_{\triangle}(\cdot,\cdot)$ operation. Recall that we denoted
$\text{bit}_{\triangle}(\alpha,\beta)$ as the first bit after the period in
which they differ, where $\alpha=0.\alpha_{1}\alpha_{2}...$, and
$\beta=0.\beta_{1}\beta_{2}...$. By using
$\text{bit}_{\triangle}(\cdot,\cdot)$ on the centers of $\square$ and
$\widehat{\square}$, we can obtain the level then length of their smallest
common canonical square $\widetilde{\square}$. Once we get the length, we can
cast the center of $\square$ to the bottom-left corner of
$\widetilde{\square}$ to obtain $\widetilde{\square}$. The above description
was summarised in the below corollary from [10].

######  Corollary 2.17 (from [10]).

Assuming that the $\text{bit}_{\triangle}$ operation and the
$\lfloor\cdot\rfloor$ operation can be performed in constant time, then one
can compute the LCA (smallest canonical square) of two points (or cells) in
constant time. Similarly, their $\mathcal{Z}$-order can be resolved in
constant time.

Being able to resolve the ordering of two canonical squares in $O(1)$ time,
one can store these canonical squares in a sorted, balanced binary data
structure. Therefore we have the below theorem from [10].

######  Theorem 2.22 (from [10]).

Assuming one can compute the $\mathcal{Z}$-order (of two points or cells) in
constant time, then one can maintain a compressed quadtree of a set of points
in $O(\log n)$ time per operation, where insertions, deletions, and point-
location query are supported. Furthermore, this can be implemented using any
data structure for ordered-set that supports an operation (insert, delete, and
point-location query) in logarithmic time.

Our compressed quadtree can handle insert operation using Algorithm 3. The
invariants maintained by the algorithm are the density value and the fact that
each internal node stores its intersecting and associated segments.

Algorithm 3 Insert

1:$s$: a segment in $\mathbb{R}^{2}$; $qt$: a compressed quadtree; $\lambda$:
the $3$-approximation of the density value of segments in $qt$.

2:$squares$ $\leftarrow$ the canonical squares split from $Q_{s}^{\prime}$

3:Insert $squares$ into $qt$ (using Theorem 2.22), and merge two squares if
they exist in $qt$.

4:for each $v$ in the inserted nodes do

5: $v_{p}\leftarrow$ the parent of $v$

6: Add intersecting segments of $v_{p}$ that are longer than or equals to
$\left\lvert s\right\rvert$ as intersecting segments of $v$

7: for each descendant $d$ of $v$ do

8: insert $s$ as the intersecting segments of $d$ if $\square_{d}$ intersects
$s$

9: $\lambda\leftarrow$ max($\lambda$, 3-approximation($\square_{v}$,
$S^{\prime}$))

10:return $\lambda$

######  Theorem B.1.

Insert operation, Algorithm 3, takes worst case $O(\lambda n)$ time, and
amortized $O(\log n+\lambda^{2}$) time per segment, and can be used to update
the $3$-approximation of the $\lambda$-low-density value in the same time.

######  Proof B.2.

The correctness of inserting a canonical square into a compressed quadtree is
shown in Theorem 2.22 from [10].

We focus on proving that the insert operation correctly maintains the lists of
intersecting segments of $\mathcal{T}$. We know that a segment $s$ can only
intersect $\square$ if $s$ intersects a canonical square containing $\square$.
Therefore for each inserted node $v$, every segment that intersects
$\square_{v}$ must be part of the intersecting segments of $\square_{v_{p}}$.
Thus we only need to visit $v_{p}$ to retrieve the intersecting segments of
$v$. And by using the same reasoning, only the descendants of $v$ can
intersect $s$, and we can preserve the decreasing order of the intersecting
segments of $v$ by using a binary insertion.

According to Theorem 2.22 from [10], inserting $O(1)$ canonical squares into a
quadtree takes $O(\log n)$ time. Recall that in Corollary 3.7, we showed that
the number of segments that intersect any bounding box with side length at
most a constant times the length of $s$ is $O(\lambda)$. Therefore each node
of $\mathcal{T}$ contains $O(\lambda)$ intersecting segments. Thus, for each
inserted node $v$, iterating over the intersecting segments of $v_{p}$ takes
$O(\lambda)$ time. And inserting $s$ as the intersecting segments of any node
takes $O(\log\lambda)$ using binary insertion.

What remains is to upper-bound how many nodes we need to insert $s$ into. In
the worst case, we may need to insert $s$ into $O(n)$ nodes. Running our
$3$-approximation algorithm on $n$ nodes takes $O(\lambda n)$ time. Therefore
the insert operation takes worst case $O(\log n+n\log\lambda+\lambda
n)\subseteq O(\lambda n)$ time.

However, we can argue that on average, we only update $O(\lambda)$ nodes per
insert. Since each $Q_{s}^{\prime}$ intersects $O(\lambda)$ segments, after
$n$ consecutive insert operations, we insert only $O(\lambda n)$ segments as
the intersecting segments of various nodes. Therefore we insert $s$ into
$O(\lambda)$ nodes on average. The amortized time of each insert operation is
$O(\log n+\lambda\log\lambda+\lambda^{2})\subseteq O(\log n+\lambda^{2})$.
This completes the proof.

##  Appendix C Appendix: Experiments

We implemented a simple algorithm to obtain the $4$-approximate density values
on several trajectory data sets. The algorithm is a simplification of the
3-approximation algorithm presented in Section 2.2.

The data sets were provided to us by the authors of [9]. Each data set
contains a number of trajectories. Table 3 summarises the data sets, and its
information is taken from [9]. This experiment aims to show the practicality
of our approximation method and motivate the study of low density. By
estimating the density values of real-world trajectories, we hope to show that
many curves are low-density; therefore, the notion of low density is a
practical, realistic input model.

Table 3: Real data sets containing trajectories in $\mathbb{R}^{2}$, showing number of input trajectories $n$, average number of vertices per trajectory, and a description Data set | $n$ | #Vertices | Trajectory Description
---|---|---|---
Vessel-M [12] | 106 | 23.0 | MS River USA shipping vessels Shipboard AIS.
Vessel-Y [12] | 187 | 155.2 | Yangtze River shipping vessels Shipboard AIS.
Truck [6] | 276 | 406.5 | GPS of 50 concrete trucks in Athens, Greece.
Bus [6] | 148 | 446.6 | GPS of School buses.
Taxi [19, 20] | 180,736 | 75.7 | Beijing taxi trajectories split into trips.
Geolife [23, 21, 22] | 18,670 | 1,332.5 | People movement, mostly in Beijing, China.
Pigeon [7] | 131 | 970.0 | Homing Pigeons (release sites to home site).
Seabird [13] | 134 | 3,175.8 | GPS of Masked Boobies in Gulf of Mexico.
Cats [11] | 154 | 526.1 | Pet house cats GPS in RDU, NC, USA.
Buffalo [3] | 165 | 161.3 | Radio-collared Kruger Buffalo, South Africa.
Gulls [18] | 253 | 602.1 | Black-backed gulls GPS (Finland to Africa).
Bats [8] | 545 | 127.2 | Video-grammetry of Daubenton trawling bats.

###  C.1 Experimental setup

We used the 4-approximation algorithm to estimate the density values of the
trajectories in each data set. We record the total number of curves, the
maximum curve size, the max, and median estimate density values, and the
median density to curve size ratio for each data set. We summarise the
information in Table 4. We present the distributions of estimate density
values in Figure 8 and 9.

Table 4: The table lists $4$-approximate density values of $12$ data sets. The second and third columns show the number of curves and the maximum curve size. The following two columns shows the maximum and median density value. The last column shows the median ratio between $\lambda$ and the size of the curve $n$.  Data set | #Curves | MaxCurveSize | Max | Median | Median $\lambda/n$
---|---|---|---|---|---
Vessel-M | 102 | 142 | 17 | 2.0 | 0.133
Vessel-Y | 186 | 559 | 3 | 3.0 | 0.020
Truck | 272 | 991 | 45 | 11.0 | 0.028
Bus | 144 | 1015 | 17 | 7.0 | 0.016
Taxi | 947 | 3340 | 682 | 14 | 0.091
GeoLife | 999 | 64482 | 335 | 5 | 0.011
Pigeon | 130 | 1645 | 665 | 28.0 | 0.038
Seabird | 133 | 8556 | 1483 | 351 | 0.131
Cat | 153 | 11122 | 411 | 45 | 0.224
Buffalo | 162 | 479 | 82 | 21.0 | 0.169
Gull | 126 | 16019 | 1520 | 50.5 | 0.159
Bat | 544 | 735 | 8 | 2.0 | 0.020

Figure 8: Distributions of approximate density values of trajectories in
Vessel-M, Vessel-Y, Truck, Bus, Taxi, and GeoLife data sets

Figure 9: Distributions of approximate density values of trajectories in
Pigeon, Seabird, Cat, Buffalo, Gull, and Bat data sets

###  C.2 Discussion

In the experiment, we estimated the density values of trajectories in twelve
real-world data sets. Our observation is that most of the data sets’ estimated
density values are low. In eleven data sets (all except Seabird), the median
estimate density values are less than $51$. In six data sets, Vessel-Y, Truck,
Bus, GeoLife, Pigeon, and Bat, the median $\lambda/n$ ratios are less than
$0.04$, where $\lambda$ and $n$ are the estimated density value and the size
of the curve. Although the density values are estimates, the notion of low
density for trajectories is valuable. The algorithms that perform better when
the density value is small, e.g. the algorithm by Driemel et al. [5], can be
applied to these data sets to improve efficiency.