# Tracking charged particles in the zero curvature limit

J. Alcaraz Maestre
CIEMAT-Madrid

(CIEMAT Technical Report 1487 111ISBN/ISSN: 2695-8864, NIPO: 832-21-005-X,
CIEMAT, September 2021, https://cpage.mpr.gob.es/ )

###### Abstract

In this report we discuss appropriate strategies for the tracking of charged
particles in the limit of zero curvature. The suggested approach avoids
special treatments and precision issues that frequently arise in that limit.
We provide explicit expressions for transport, refitting and vertexing in
regions where magnetic field inhomogeneities or detector interaction effects
can be approximately ignored.

##  1 Introduction

The linear relation between the transverse momentum $p_{T}$ of a charged
particle and the inverse of its curvature $C$ in the presence of a magnetic
field constitutes the basis for the determination of momenta in particle
physics. This relation is typically exploited by tracking and analyzing the
ionization deposits along the trajectory of the particle. Sophisticated
tracking techniques in past and present experiments have resulted into major
physical results and discoveries. Getting sufficiently precise measurements
will become particularly challenging at future colliders with multi-TeV
center-of-mass energies, due to the much lower expected curvatures. In this
context, ultra-precise detectors with $\lesssim 10~{}\mathrm{\mu m}$ of
position and alignment accuracies over distances of meters, able to support
high occupancies of hundreds or even thousands of tracks per event will be
required.

The zero curvature limit ($C\rightarrow 0$) or, equivalently, the transverse
momentum limit ($p_{T}\rightarrow\infty$) is always a potential source of
problems for tracking algorithms, due to presence of divergent operations in
many of the used equations. A dangerous approach is to consider $C=0$ as a
special, exceptional case. The problem occurs in practice when the curvature
gets smaller or comparable to the computer precision used in the calculations,
$\mathcal{C}_{prec}$. Apart from the inherent complications in the code, the
scheme is intrinsically limited because it abandons by construction the
possibility of providing sensible measurements for tracks with
$C<\mathcal{C}_{prec}$.

This report discusses tracking in the zero curvature limit, based on some past
notes written in the running period of the L3 detector at LEP [1]. It adopts
the basic strategy of avoiding the use of any curvature threshold in a
systematic way. For that, we work at all times with relatively simple
expressions that do not present divergences in the $C\rightarrow 0$ limit.
This turns out to be optimal to obtain precise measurements at high momenta.
The resulting equations were successfully employed already in past tracking
and detector alignment algorithms, starting with the L3 detector at LEP [2, 1,
3, 4].

Only tracking in homogeneous magnetic fields is considered, but one has to
keep in mind that all inhomogeneous cases are decomposed in practice into a
series of small propagation steps where the present formulae are always
applicable. Material effects, which are more frequently discussed in
connection with filtering techniques [5], do not have an influence on the
choice of the parametrization near the collision point. Specific approaches to
the case of slightly inhomogeneous magnetic fields are discussed for instance
in References [6, 7].

The document is organized as follows. Section 2 introduces the “perigee”
parametrization that will be used throughout most of the report. It also
connects it with other equivalent conventions used in the literature. The
propagation of track parameters and related uncertainties is discussed in
sections3 4, including specific subsections for the cases of propagation to
cylinder and plane surfaces (sections 4.4 and 4.5). Sections 5 and 5.3 address
the typical problem of track refitting when new measurements are present,
which is of utmost importance in alignment, fitting and filtering techniques
in general. Finally, sections 6 and 7 discuss vertex determination in a simple
but precise way.

##  2 Conventions

A helix is the most general trajectory followed by a charged particle in a
homogeneous, constant in time, magnetic field region in vacuum. We assume that
the direction of the magnetic field coincides with the positive direction of
the Z axis in the reference system. The trajectory can thus be visualized in
XY as a circumference (Figure 1). The Z displacement between two positions in
the trajectory is proportional to the arc length that is described in the XY
plane, leading to the concept of a “straight line in the SZ plane”, where S
identifies the variable associated to the arc length (Figure 2). Unless
otherwise stated, equations assume that distances are given in meters,
magnetic field strengths in Teslas, charge in units of the positron charge and
momenta in GeV/$c$. We will consider a standard decomposition of the local
momentum vector, $\hat{p}$, in spherical coordinates:
$\hat{p}\equiv(p\sin\theta\cos\phi,p\sin\theta\sin\phi,p\cos\theta)$, where
$p$ is its magnitude and $\phi$ and $\theta$ are the associated azimuthal and
polar angles. Since the magnetic field is homogeneous and does not change with
time, $p$ and $\theta$ are constants of motion. The angles are chosen such
that: $\phi\in(-\pi,\pi]$ and $\theta\in[0,\pi]$.

In the XY plane the trajectory can be fully described by a reference point,
$(x_{r},y_{r})$, and three parameters, $C$, $\phi_{0}$ and $\delta$ (Figure
1):

Figure 1:  The projection of the track helix on the XY plane will be a
circumference. The parameters shown in the figure are described in the text.

  * •

$C$: the curvature of the track. It is related with the absolute value of the
transverse momentum $p_{T}$ via the Equation: $C=0.29979~{}\mathrm{Bq}/p_{T}$,
where B is the magnetic field strength and $q$ the particle charge. The
curvature is positive (negative) if the particle has a positive (negative)
charge. A positive (negative) curvature identifies a clockwise (anti-
clockwise) rotation of the particle in the XY coordinate system as a function
of time.

  * •

$\phi_{0}$: the azimuthal angle of the momentum vector at the position of
closest approach to the reference point.

  * •

$\delta$: the distance of closest approach to the reference point. This is a
signed parameter, with a convention such that the coordinates of closest
approach $(x_{0},y_{0})$ are given by:

$\displaystyle\left.\begin{array}[]{c}x_{0}=x_{r}-\delta\sin\phi_{0}\\\
y_{0}=y_{r}+\delta\cos\phi_{0}\\\ \end{array}\right\\}$
$\displaystyle\Longrightarrow$
$\displaystyle~{}\delta=-(x_{0}-x_{r})\sin\phi_{0}+(y_{0}-y_{r})\cos\phi_{0}$
(3)

The trajectory in the SZ plane is simply described by a straight line:

$\displaystyle z$ $\displaystyle=$ $\displaystyle z_{0}+s~{}\tan\lambda$ (4)

where $s$ is the arc length traversed when the particle moves from
$(x_{0},y_{0})$ to $(x,y)$ and the parameters $\tan\lambda$ and $z_{0}$ have a
simple interpretation (Figure 2):

  * •

$\tan\lambda$: the slope in the SZ plane, $dz/ds$. It is directly related with
the polar angle $\theta$ by: $\tan\lambda=1/\tan\theta$.

  * •

$z_{0}$: the Z position when the particle is at the distance of closest
approach in the XY plane.

Figure 2: Following the adopted convention, the projection of the track on the
SZ plane will be a straight line: $z=z_{0}+s\tan\lambda$. The relevant
parameters are shown in the Figure. Note that the variable $s$ at a point
$(x,y,z)$ is equal to the arc length in the XY plane between $(x_{0},y_{0})$
to $(x,y)$. This also implies that $s=0$ at $z=z_{0}$.

Let us note that the arc length $s$ can be either positive or negative,
depending on whether $(x,y)$ corresponds to a position occurring before or
after $(x_{0},y_{0})$ in time.

In summary, in this “perigee” convention, a track is fully defined by a
reference point $(x_{r},y_{r})$ and the set of parameters
$(C,\phi_{0},\delta,z_{0},\tan\lambda)$. This is the convention used for
instance by the CMS [8] and L3 [2] experiments to describe track parameters
and uncertainties close to the interaction point 222The L3 parametrization was
only differing by a change in the sign convention for the $\delta$ parameter..
According to the previous discussion, $C$ and $\tan\lambda$ are constant over
the trajectory.

###  2.1 Alternative parametrizations

There are equivalent parametrizations in the literature, already used in past
or existing high-energy physics experiments. They differ slightly from the one
employed in this report:

  * •

An alternative perigee parametrization [9], rather similar to our choice. The
most relevant difference is the use of the parameter $\theta$ instead of
$\tan\lambda$. Both parameters are constant in the case of homogeneous fields,
but $\tan\lambda$ is the slope of the straight line fit in the SZ plane, a
technically natural coefficient for detectors embedded in a solenoidal field.
Explicitly, this alternative choice employs the parameters $\rho$, $\phi_{p}$,
$\epsilon$, $\theta$ and $z_{p}$, which are connected with our parameters
through the relations: $\rho=-C$, $\phi_{p}=\phi_{0}$, $\epsilon=-\delta$,
$\cot\theta=\tan\lambda$, $z_{p}=z_{0}$.

  * •

A variation of the previous “perigee” parametrization [9] is the one described
for instance in Reference [10], which is used in ATLAS [11]. It basically
substitutes the curvature $C$ by the inverse of the transverse rigidity,
$\mathrm{q}/p_{T}$. The relation between the curvature and $\mathrm{q}/p_{T}$
is: $\mathrm{q}/p_{T}=(C~{}\cos\lambda)/(0.29979~{}\mathrm{B})$. Note that
this parametrization requires the a priori knowledge of the magnetic field
strength, something that is not intrinsically necessary to reconstruct tracks
in regions with homogeneous magnetic fields and negligible interactions with
the medium.

  * •

The curvilinear parametrization [12] adopts a local description of the track
with the parameters $(q/p,\phi,x_{\perp},\lambda,z_{\perp})$. Here $x_{\perp}$
and $z_{\perp}$ quantify displacements in a plane transverse to the
trajectory. When the point on the track is the one with closest transverse
approach with respect to $(x_{r},y_{r})$: $\phi=\phi_{0}$, $x_{\perp}=\delta$
and $z_{\perp}=z_{0}\cos\lambda$.

All equations presented in this report can be adapted to any of these
alternative parametrizations in a straightforward way. For completeness, we
also collect in Appendix A the Jacobians of the transformations to the
alternative conventions. These Jacobians are required for the propagation of
the uncertainties discussed in Section 4.

##  3 Some useful formulae for propagation algorithms in the zero-curvature
limits

Most of the problems encountered in propagation algorithms admit several
solutions from a formal point of view. However, many of these solutions are
not optimal, neither from the point of view of precision, nor from the point
of view of simplicity. The relations shown below are free of divergences in
the $C\rightarrow 0$ limit.

###  3.1 Determining the azimuthal angle of the trajectory at a given point in
the transverse plane.

If the curvature is already available, an optimal expression to determine
$\phi$ is the following:

$\displaystyle\phi$ $\displaystyle=$
$\displaystyle\mathrm{atan2}\left(\sin\phi_{0}-C~{}(x-x_{0}),\cos\phi_{0}+C~{}(y-y_{0})\right)$
(5)

where $\mathrm{atan2}(y,x)$ is the function that returns the azimuthal angle
of the vector $(x,y)$ in the range $(-\pi,\pi]$. If one prefers not to use
$C$, an alternative expression is:

$\displaystyle\phi$ $\displaystyle=$
$\displaystyle\mathrm{InRange}(2~{}\mathrm{atan2}(y-y_{0},x-x_{0})-\phi_{0})$
(6)

where $\mathrm{InRange}(\phi)$ is the function that brings the angle $\phi$
into the $(-\pi,\pi]$ range:

$\displaystyle\mathrm{InRange}(\phi)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{lrl}\phi+2\pi~{}\mathrm{int}(0.5-\frac{\phi}{2\pi})&\hfil&{\rm,for}~{}\phi\leq\pi\\\
\phi-2\pi~{}\mathrm{int}(0.5+\frac{\phi}{2\pi})&\hfil&{\rm,for}~{}\phi>\pi\end{array}\right.$
(9)

Here $\mathrm{int}(x)$ is the integer part of the real number $x$. Both
Equations, 5 and 6, give a precise answer in the $C\rightarrow 0$ limit.

###  3.2 Curvature when only two points in the transverse plane and the
azimuthal angle at one of these points are known.

The optimal and shortest answer for this problem is:

$\displaystyle C$ $\displaystyle=$
$\displaystyle\frac{2(x-x_{0})\sin\phi_{0}-2(y-y_{0})\cos\phi_{0}}{(x-x_{0})^{2}+(y-y_{0})^{2}}$
(10)

where $\phi_{0}$ is the azimuthal angle at the point $(x_{0},y_{0})$ and
$(x,y)$ is a second point on the trajectory.

###  3.3 Arc length at a given point of the trajectory.

If we define the following projected components of the distance between the
point of closest transverse approach $(x_{0},y_{0})$ and the given point
$(x,y)$:

$\displaystyle\Delta_{\parallel}$ $\displaystyle=$
$\displaystyle(x-x_{0})\cos\phi_{0}+(y-y_{0})\sin\phi_{0}$ (11)
$\displaystyle\Delta_{\perp}$ $\displaystyle=$
$\displaystyle-(x-x_{0})\sin\phi_{0}+(y-y_{0})\cos\phi_{0},$ (12)

we obtain the solution, well behaved in the zero curvature limit:

$\displaystyle
s=\frac{\mathrm{atan2}(C~{}\Delta_{\perp},1+C~{}\Delta_{\parallel})}{C}$ (13)

If we have access to the local azimuthal angle $\phi$ at $(x,y)$ (see also
subsection 3.1), we can use instead a relation that is totally independent of
$C$:

$\displaystyle s$ $\displaystyle=$
$\displaystyle\frac{\Delta_{\parallel}}{\mathrm{sinc}(\phi-\phi_{0})}$ (14)

where $\mathrm{sinc}(x)$ is the function $(\sin x)/x$.

###  3.4 Determining the position on the trajectory for a given arc length.

To avoid accuracy problems one should use the curvature $C$ in a special way:

$\displaystyle x$ $\displaystyle=$ $\displaystyle
x_{0}+s~{}\mathrm{sinc}\left(\frac{Cs}{2}\right)\cos\left(\phi_{0}-\frac{Cs}{2}\right)$
(15) $\displaystyle y$ $\displaystyle=$ $\displaystyle
y_{0}+s~{}\mathrm{sinc}\left(\frac{Cs}{2}\right)\sin\left(\phi_{0}-\frac{Cs}{2}\right),$
(16)

If $\phi$ is available, one can make the substitution: $Cs=\phi_{0}-\phi$, and
use instead:

$\displaystyle x$ $\displaystyle=$ $\displaystyle
x_{0}-s~{}\mathrm{sinc}\left(\frac{\phi-\phi_{0}}{2}\right)\cos\left(\frac{\phi+\phi_{0}}{2}\right)$
(17) $\displaystyle y$ $\displaystyle=$ $\displaystyle
y_{0}-s~{}\mathrm{sinc}\left(\frac{\phi-\phi_{0}}{2}\right)\sin\left(\frac{\phi+\phi_{0}}{2}\right),$
(18)

##  4 Propagation of track parameters and uncertainties

In this section we provide expressions to update the track parameters and the
associated covariance matrix when a new reference point
$(x_{r}^{\prime},y_{r}^{\prime},z_{r}^{\prime})$, different from the original
one $(x_{r},y_{r},z_{r})$, is used in the parametrization (Figure 3). There
are two important use cases that are covered with this exercise: a) a track
referred to a new point that is different from the initial estimate used in
reconstruction (typically the beam spot); b) the propagation to the crossing
point between the track and any given subdetector surface.

Figure 3:  Change of parameters in XY when the reference point moves from
$(x_{r},y_{r})$ to $(x_{r}^{\prime},y_{r}^{\prime})$.

###  4.1 Updated track parameters at a new reference point

Changing the reference point of a track implies a modification of its
parameters $\phi_{0}$, $\delta$ and $z_{0}$. We will denote the new parameters
by $\phi_{0}^{\prime}$, $\delta^{\prime}$ and $z_{0}^{\prime}$. Since
$\mathrm{sign(1-C\delta)=sign(1-C\delta^{\prime})}$ for all cases of practical
interest, $\phi_{0}^{\prime}$ can be unambiguously determined as follows:

$\displaystyle\phi_{0}^{\prime}=\mathrm{atan2}\left(\sin\phi_{0}-\frac{C\Delta_{x}}{1-C\delta},\cos\phi_{0}+\frac{C\Delta_{y}}{1-C\delta}\right)$
(19)

where $\Delta_{x}=x_{r}^{\prime}-x_{r}$ and $\Delta_{y}=y_{r}^{\prime}-y_{r}$.
Once $\phi_{0}^{\prime}$ is available, a convenient expression to determine
$\delta^{\prime}$, also with a good behavior in the $C\rightarrow 0$ limit,
is:

$\displaystyle\delta^{\prime}$ $\displaystyle=$
$\displaystyle\delta+\Delta_{x}\sin\phi_{0}-\Delta_{y}\cos\phi_{0}+(\Delta_{x}\cos\phi_{0}+\Delta_{y}\sin\phi_{0})\tan(\frac{\phi_{0}^{\prime}-\phi_{0}}{2})$
(20)

The point of minimum transverse approach to $(x_{r}^{\prime},y_{r}^{\prime})$
is then simply given by:

$\displaystyle x_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
x_{r}^{\prime}-\delta^{\prime}\sin\phi_{0}^{\prime}$ (21) $\displaystyle
y_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
y_{r}^{\prime}+\delta^{\prime}\cos\phi_{0}^{\prime},$ (22)

leading to the following expression for the determination of the
$z_{0}^{\prime}$ parameter:

$\displaystyle z_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
z_{0}+\frac{(x_{0}^{\prime}-x_{0})\cos\phi_{0}+(y_{0}^{\prime}-y_{0})\sin\phi_{0}}{\mathrm{sinc}(\phi_{0}^{\prime}-\phi_{0})}~{}\tan\lambda$
(23)

###  4.2 Approximate solutions for the distance of closest approach to a given
point

Equation 20 can be well approximated in the $C\delta^{\prime}\muchless 1$
limit, i.e. when the new reference point is very close to the particle
trajectory:

$\displaystyle\delta^{\prime}\approx\delta-\frac{C\delta^{2}}{2}+\left(\Delta_{x}\sin\phi_{0}-\Delta_{y}\cos\phi_{0}\right)~{}(1-C\delta)-C~{}\frac{\Delta_{x}^{2}+\Delta_{y}^{2}}{2}$
(24)

where the neglected term on the right hand side is $C\delta^{\prime 2}/2$. The
expression can be further simplified if $C\delta^{2}$ and
$C\delta\delta^{\prime}$ terms are also negligible:

$\displaystyle\delta^{\prime}\approx\delta+\Delta_{x}\sin\phi_{0}-\Delta_{y}\cos\phi_{0}-\frac{C}{2(1-C\delta)}~{}\left(\Delta_{x}^{2}+\Delta_{y}^{2}\right)$
(25)

This approximation can be used as the starting point for the determination of
the track parameters $C,\phi_{0},\delta$ [13]. It is indeed one of the
preferred methods when energy losses are not important, and it was
successfully employed in several past high-energy physics experiments.

###  4.3 Updated covariance matrix after propagation to a new point or surface

The new covariance matrix after propagation, $V^{\prime}$, can be determined
in a linear approximation as:

$\displaystyle V^{\prime}$ $\displaystyle=$ $\displaystyle
J\left(\frac{\partial(C^{\prime},\phi_{0}^{\prime},\delta^{\prime},\tan\lambda^{\prime},z_{0}^{\prime})}{\partial(C,\phi_{0},\delta,\tan\lambda,z_{0})}\right)~{}V~{}J\left(\frac{\partial(C^{\prime},\phi_{0}^{\prime},\delta^{\prime},\tan\lambda^{\prime},z_{0}^{\prime})}{\partial(C,\phi_{0},\delta,\tan\lambda,z_{0})}\right)^{T}$
(26)

where $J$ is the Jacobian matrix of the transportation, $J^{T}$ its transpose
and $V$ is the original covariance matrix. We will implicitly assume that the
full covariance matrix can be built separately in the XY and SZ projections.
This is a good approximation if: a) no significant correlations exist between
measurements in the XY and SZ planes or b) measurements in the XY place are
much more precise than measurements in the SZ plane. Both conditions are
generally satisfied in high-energy particle detectors. Condition b) is
satisfied by design in most cases of interest because the best precision is
always required in the plane that measures the transverse momentum, i.e. XY.
Condition a) is satisfied when active detectors adopt an axial geometry around
accelerator beams. An exception is the case of silicon microstrip detectors
with slightly tilted stereo-layers 333This tilt corresponds to a small
rotation around the $(\cos\phi_{d},\sin\phi_{d},0)$ direction, where
$\phi_{d}$ is the azimuthal angle of the center of the layer at $z=0$.. In
this case, condition b) is approximately satisfied, the influence of SZ
parameter uncertainties on the XY fit can be neglected and the arc lengths
described in the XY plane can be considered as extremely precise compared with
Z uncertainties in the SZ straight line fit.

The Jacobian matrix can be therefore expressed as:

$\displaystyle
J\left(\frac{\partial(C^{\prime},\phi_{0}^{\prime},\delta^{\prime},\tan\lambda^{\prime},z_{0}^{\prime})}{\partial(C,\phi_{0},\delta,\tan\lambda,z_{0})}\right)$
$\displaystyle\equiv$
$\displaystyle\left(\begin{array}[]{c|c|c|c|c}\frac{\partial
C^{\prime}}{\partial C}&\frac{\partial
C^{\prime}}{\partial\phi_{0}}&\frac{\partial
C^{\prime}}{\partial\delta}&0&0\\\ \frac{\partial\phi_{0}^{\prime}}{\partial
C}&\frac{\partial\phi_{0}^{\prime}}{\partial\phi_{0}}&\frac{\partial\phi_{0}^{\prime}}{\partial\delta}&0&0\\\
\frac{\partial\delta^{\prime}}{\partial
C}&\frac{\partial\delta^{\prime}}{\partial\phi_{0}}&\frac{\partial\delta^{\prime}}{\partial\delta}&0&0\\\
0&0&0&\frac{\partial\tan\lambda^{\prime}}{\partial\tan\lambda}&\frac{\partial\tan\lambda^{\prime}}{\partial
z_{0}}\\\ 0&0&0&\frac{\partial
z_{0}^{\prime}}{\partial\tan\lambda}&\frac{\partial z_{0}^{\prime}}{\partial
z_{0}}\end{array}\right)$ (32)

After careful processing of all terms with a potentially bad behavior in the
straight line limit we obtain for the XY sub-matrix associated to XY
measurements:

$\displaystyle\frac{\partial C^{\prime}}{\partial C}$ $\displaystyle=$
$\displaystyle 1$ (33) $\displaystyle\frac{\partial
C^{\prime}}{\partial\phi_{0}}$ $\displaystyle=$ $\displaystyle 0$ (34)
$\displaystyle\frac{\partial C^{\prime}}{\partial\delta}$ $\displaystyle=$
$\displaystyle 0$ (35) $\displaystyle\frac{\partial\phi_{0}^{\prime}}{\partial
C}$ $\displaystyle=$
$\displaystyle-\frac{1}{(1-C\delta^{\prime})^{2}}~{}(\Delta_{x}\cos\phi_{0}+\Delta_{y}\sin\phi_{0})$
(36) $\displaystyle\frac{\partial\phi_{0}^{\prime}}{\partial\phi_{0}}$
$\displaystyle=$
$\displaystyle\left(\frac{1-C\delta}{1-C\delta^{\prime}}\right)+\frac{C^{2}(1-C\delta)}{2(1-C\delta^{\prime})^{2}}~{}(\delta^{\prime
2}-(\Delta_{x}+\delta\sin\phi_{0})^{2}-(\Delta_{y}-\delta\cos\phi_{0})^{2})$
(37) $\displaystyle\frac{\partial\phi_{0}^{\prime}}{\partial\delta}$
$\displaystyle=$
$\displaystyle-\frac{C^{2}}{(1-C\delta^{\prime})^{2}}~{}(\Delta_{x}\cos\phi_{0}+\Delta_{y}\sin\phi_{0})$
(38) $\displaystyle\frac{\partial\delta^{\prime}}{\partial C}$
$\displaystyle=$
$\displaystyle\frac{1}{2(1-C\delta^{\prime})}~{}(\delta^{\prime
2}-(\Delta_{x}+\delta\sin\phi_{0})^{2}-(\Delta_{y}-\delta\cos\phi_{0})^{2})$
(39) $\displaystyle\frac{\partial\delta^{\prime}}{\partial\phi_{0}}$
$\displaystyle=$
$\displaystyle\frac{1-C\delta}{1-C\delta^{\prime}}~{}(\Delta_{x}\cos\phi_{0}+\Delta_{y}\sin\phi_{0})$
(40) $\displaystyle\frac{\partial\delta^{\prime}}{\partial\delta}$
$\displaystyle=$ $\displaystyle
1+\frac{C^{2}}{2(1-C\delta^{\prime})}~{}(\delta^{\prime
2}-(\Delta_{x}+\delta\sin\phi_{0})^{2}-(\Delta_{y}-\delta\cos\phi_{0})^{2})$
(41)

with a smooth transition to the straight-line track limit:

$\displaystyle\frac{\partial C^{\prime}}{\partial C}$ $\displaystyle=$
$\displaystyle 1$ (42) $\displaystyle\frac{\partial
C^{\prime}}{\partial\phi_{0}}$ $\displaystyle=$ $\displaystyle 0$ (43)
$\displaystyle\frac{\partial C^{\prime}}{\partial\delta}$ $\displaystyle=$
$\displaystyle 0$ (44) $\displaystyle\frac{\partial\phi_{0}^{\prime}}{\partial
C}$ $\displaystyle=$
$\displaystyle-(\Delta_{x}\cos\phi_{0}+\Delta_{y}\sin\phi_{0})$ (45)
$\displaystyle\frac{\partial\phi_{0}^{\prime}}{\partial\phi_{0}}$
$\displaystyle=$ $\displaystyle 1$ (46)
$\displaystyle\frac{\partial\phi_{0}^{\prime}}{\partial\delta}$
$\displaystyle=$ $\displaystyle 0$ (47)
$\displaystyle\frac{\partial\delta^{\prime}}{\partial C}$ $\displaystyle=$
$\displaystyle\frac{1}{2}~{}(\delta^{\prime
2}-(\Delta_{x}+\delta\sin\phi_{0})^{2}-(\Delta_{y}-\delta\cos\phi_{0})^{2})$
(48) $\displaystyle\frac{\partial\delta^{\prime}}{\partial\phi_{0}}$
$\displaystyle=$
$\displaystyle(\Delta_{x}\cos\phi_{0}+\Delta_{y}\sin\phi_{0})$ (49)
$\displaystyle\frac{\partial\delta^{\prime}}{\partial\delta}$ $\displaystyle=$
$\displaystyle 1$ (50)

The derivatives required to build the $(\tan\lambda,z_{0})$ covariance sub-
matrix are simpler:

$\displaystyle\frac{\partial\tan\lambda^{\prime}}{\partial\tan\lambda}$
$\displaystyle=$ $\displaystyle 1$ (51)
$\displaystyle\frac{\partial\tan\lambda^{\prime}}{\partial z_{0}}$
$\displaystyle=$ $\displaystyle 0$ (52) $\displaystyle\frac{\partial
z_{0}^{\prime}}{\partial\tan\lambda}$ $\displaystyle=$ $\displaystyle s$ (53)
$\displaystyle\frac{\partial z_{0}^{\prime}}{\partial z_{0}}$ $\displaystyle=$
$\displaystyle 1$ (54)

For other track parametrizations (see section 2.1), an additional conversion
will be necessary: $V_{par}^{\prime}=J_{par}~{}V_{par}~{}J_{par}^{T}$, where
$V_{par}$ is the covariance matrix of the alternative parametrization and
$J_{par}$ is related with the Jacobian matrices given in Appendix A via the
formula:

$\displaystyle J_{par}$ $\displaystyle=$ $\displaystyle
J\left(\frac{\partial(\mathrm{new~{}par.})}{\partial(C,\phi_{0},\delta,\ldots)}\right)~{}J\left(\frac{\partial(C^{\prime},\phi_{0}^{\prime},\delta^{\prime},\ldots)}{\partial(C,\phi_{0},\delta,\ldots)}\right)~{}J\left(\frac{\partial(\mathrm{new~{}par.})}{\partial(C,\phi_{0},\delta,\ldots)}\right)^{-1}$
(55)

###  4.4 Track crossing a cylinder with axis parallel to Z

The case is illustrated in Figure 4. The crossing point
$(x_{0}^{\prime},y_{0}^{\prime},z_{0}^{\prime})$ is defined by the conditions:

$\displaystyle C~{}x_{0}^{\prime}+\sin\phi_{0}^{\prime}$ $\displaystyle=$
$\displaystyle C~{}x_{0}+\sin\phi_{0}$ (56) $\displaystyle
C~{}y_{0}^{\prime}-\cos\phi_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
C~{}y_{0}-\cos\phi_{0}$ (57) $\displaystyle z_{0}^{\prime}$ $\displaystyle=$
$\displaystyle z_{0}+s~{}\tan\lambda$ (58) $\displaystyle\rho^{2}$
$\displaystyle=$
$\displaystyle(x_{0}^{\prime}-x_{\rho})^{2}+(y_{0}^{\prime}-y_{\rho})^{2}$
(59)

Figure 4: XY projection of a track crossing a cylinder with axis parallel to
the Z axis.

where $(x_{\rho},y_{\rho})$ is the center of the circumference being crossed
in the XY plane and $\rho$ is its radius. To solve the system of equations we
use the following definitions:

$\displaystyle\phi_{\rho}$ $\displaystyle=$
$\displaystyle\mathrm{atan2}\left(\sin\phi_{0}-C(x_{\rho}-x_{0}),\cos\phi_{0}+C(y_{\rho}-y_{0})\right)$
(60) $\displaystyle\phi_{c}$ $\displaystyle=$
$\displaystyle\mathrm{atan2}\left(y_{0}^{\prime}-y_{\rho},x_{0}^{\prime}-x_{\rho}\right)$
(61) $\displaystyle\gamma$ $\displaystyle=$
$\displaystyle\frac{2(x_{\rho}-x_{0})\sin\phi_{0}-2(y_{\rho}-y_{0})\cos\phi_{0}-C\rho^{2}-C((x_{\rho}-x_{0})^{2}+(y_{\rho}-y_{0})^{2})}{2\rho\sqrt{(\sin\phi_{0}-C(x_{\rho}-x_{0}))^{2}+(\cos\phi_{0}+C(y_{\rho}-y_{0}))^{2}}}$
(62)

The implicit solution is simply:

$\displaystyle\sin(\phi_{c}-\phi_{\rho})$ $\displaystyle=$
$\displaystyle\gamma$ (63)

which has a meaning only if $\mid\gamma\mid<1$ and provides two possible
solutions for $\phi_{c}$ (as visually expected). In terms of $\phi_{c}$, the
values of $x_{0}^{\prime}$, $y_{0}^{\prime}$, $\phi_{0}^{\prime}$ and
$z_{0}^{\prime}$ are given by:

$\displaystyle x_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
x_{\rho}+\rho~{}\cos\phi_{c}$ (64) $\displaystyle y_{0}^{\prime}$
$\displaystyle=$ $\displaystyle y_{\rho}+\rho~{}\sin\phi_{c}$ (65)
$\displaystyle\phi_{0}^{\prime}$ $\displaystyle=$
$\displaystyle\mathrm{atan2}\left(\sin\phi_{0}-C(x_{0}^{\prime}-x_{0}),\cos\phi_{0}+C(y_{0}^{\prime}-y_{0})\right)$
(66) $\displaystyle z_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
z_{0}+\left[\frac{(x_{0}^{\prime}-x_{0})\cos\phi_{0}+(y_{0}^{\prime}-y_{0})\sin\phi_{0}}{\mathrm{sinc}(\phi_{0}^{\prime}-\phi_{0})}\right]~{}\tan\lambda$
(67)

In most cases we will only be interested in solutions with a positive arc
length:

$\displaystyle(x_{0}^{\prime}-x_{0})\cos\phi_{0}+(y_{0}^{\prime}-y_{0})\sin\phi_{0}>0$
(68)

In a typical scenario with a cylinder with $\rho^{2}<R^{2}$ and
$(x_{0}-x_{\rho})^{2}+(y_{0}-y_{\rho})^{2}<\rho^{2}$, i.e. a cylinder with its
center close to the distance of minimum approach, only one solution with
positive arc length exists, given by:

$\displaystyle\phi_{c}$ $\displaystyle=$
$\displaystyle\phi_{\rho}+\arcsin(\gamma)$ (69)

The covariance matrix at the new crossing point can be determined from the
equations developed in Section 4, using
$(x_{0}^{\prime},y_{0}^{\prime},z_{0}^{\prime})$ as the new reference point of
the trajectory. Note that, by construction, the reference point is sitting on
the trajectory and therefore $\delta^{\prime}=0$.

###  4.5 Track crossing a plane

This case is illustrated in Figure 5. The crossing point
$(x_{0}^{\prime},y_{0}^{\prime},z_{0}^{\prime})$ can be found from the
following conditions:

Figure 5: Parameters relevant to find the point where a track crosses a plane.
In the figure $(x_{p},y_{p},z_{p})$ is a point in the plane and
$(v_{x},v_{y},v_{z})$ is a unitary vector perpendicular to it.

$\displaystyle x_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
x_{0}+s~{}\mathrm{sinc}\left(\frac{Cs}{2}\right)\cos\left(\phi_{0}-\frac{Cs}{2}\right)$
(70) $\displaystyle y_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
y_{0}+s~{}\mathrm{sinc}\left(\frac{Cs}{2}\right)\sin\left(\phi_{0}-\frac{Cs}{2}\right)$
(71) $\displaystyle z_{0}^{\prime}$ $\displaystyle=$ $\displaystyle
z_{0}+s~{}\tan\lambda$ (72) $\displaystyle 0$ $\displaystyle=$
$\displaystyle(x_{p}-x_{0}^{\prime})~{}v_{x}+(y_{p}-y_{0}^{\prime})~{}v_{y}+(z_{p}-z_{0}^{\prime})~{}v_{z}$
(73)

where $(x_{p},y_{p},z_{p})$ is a point in the plane and $(v_{x},v_{y},v_{z})$
is a unitary vector perpendicular to it. To solve the problem we define:

$\displaystyle\phi_{v}$ $\displaystyle=$
$\displaystyle\mathrm{atan2}\left(v_{y},v_{x}\right)$ (74) $\displaystyle
v_{t}$ $\displaystyle=$ $\displaystyle\sqrt{v_{x}^{2}+v_{y}^{2}}$ (75)
$\displaystyle d_{p}$ $\displaystyle=$
$\displaystyle(x_{p}-x_{0})~{}v_{x}+(y_{p}-y_{0})~{}v_{y}+(z_{p}-z_{0})~{}v_{z}$
(76)

where $d_{p}$ is actually the signed distance from $(x_{0},y_{0},z_{0})$ to
the plane. The solution in terms of the variable $s$ can be obtained from
following equation:

$\displaystyle s$ $\displaystyle=$
$\displaystyle\frac{d_{p}}{v_{t}~{}\mathrm{sinc}\left(\frac{Cs}{2}\right)\cos\left(\frac{Cs}{2}+\phi_{v}-\phi_{0}\right)+v_{z}~{}\tan\lambda}$
(77)

which makes sense only if $|Cs|<\pi$. From a practical point of view it is
convenient to follow an iterative method converging to the solution:

$\displaystyle s_{0}$ $\displaystyle=$
$\displaystyle\frac{d_{p}}{v_{t}~{}\cos(\phi_{v}-\phi_{0})+v_{z}~{}\tan\lambda}$
(78) $\displaystyle s_{1}$ $\displaystyle=$
$\displaystyle\frac{d_{p}}{v_{t}~{}\mathrm{sinc}\left(\frac{Cs_{0}}{2}\right)\cos\left(\frac{Cs_{0}}{2}+\phi_{v}-\phi_{0}\right)+v_{z}~{}\tan\lambda}$
$\displaystyle\vdots$ $\displaystyle s_{i}$ $\displaystyle=$
$\displaystyle\frac{d_{p}}{v_{t}~{}\mathrm{sinc}\left(\frac{Cs_{i-1}}{2}\right)\cos\left(\frac{Cs_{i-1}}{2}+\phi_{v}-\phi_{0}\right)+v_{z}~{}\tan\lambda}$
(80)

Explicit solutions exist when $v_{t}=0$ or $v_{z}=0$. For $v_{t}=0$ (plane
perpendicular to the Z axis):

$\displaystyle s$ $\displaystyle=$
$\displaystyle\frac{d_{p}}{v_{z}~{}\tan\lambda},$ (81)

whereas for the $v_{z}=0$ case (plane parallel to the Z axis):

$\displaystyle\sin(Cs+\phi_{v}-\phi_{0})$ $\displaystyle=$
$\displaystyle\sin(\phi_{v}-\phi_{0})+C~{}d_{p},$ (82)

which gives two possible solutions for $s$. Only the one with minimum arc
length will be of interest in general. It is advisable to determine the final
$s$ value from $Cs$ not by division, but by substitution in Equation 77, in
order to keep the best possible accuracy.

##  5 Including new points in a track

Let us consider a new measurement $(x_{meas},y_{meas},z_{meas})$ with some
associated uncertainty. If the original track parameters and covariance matrix
are known, it is always possible to improve the parameters of a track via
$\chi^{2}$ methods. According to the approach of Section 4, we will also
assume that new measurement can be decomposed into uncorrelated measurements
in the XY and SZ planes, such that XY and SZ fitting problems can be treated
separately.

###  5.1 XY plane

Let us first redefine the track parameters using the new measurement
$(x_{meas},y_{meas},z_{meas})$ as a new reference point. The new constraint
can be interpreted as: $\delta=0\pm\sigma$, where $\sigma$ is the transverse
uncertainty on the measured position. The following $\chi^{2}$ can then be
defined:

$\displaystyle\chi^{2}$ $\displaystyle=$ $\displaystyle
x_{i}~{}S_{ij}^{0}~{}x_{j}+\left(\frac{\delta}{\sigma}\right)^{2}=x_{i}~{}S_{ij}^{0}~{}x_{j}+\left(\frac{\delta^{0}+x_{3}}{\sigma}\right)^{2}$
(83)

where $x_{1}=C-C^{0}$, $x_{2}=\phi_{0}-\phi_{0}^{0}$,
$x_{3}=\delta-\delta^{0}$, and a sum on repeated indices is assumed.
$S_{ij}^{0}$ is the inverse of the original covariance matrix, $V_{ij}^{0}$,
and $C^{0}$, $\phi_{0}^{0}$ and $\delta^{0}$ are the original values of the
track parameters extrapolated to the new reference point. The minimum of this
$\chi^{2}$ corresponds to:

$\displaystyle V_{kj}$ $\displaystyle=$
$\displaystyle\left(S_{kj}^{0}+\frac{1}{\sigma^{2}}g_{k3}g_{j3}\right)^{-1}$
$\displaystyle\Downarrow$ $\displaystyle C$ $\displaystyle=$ $\displaystyle
C^{0}-V_{13}\frac{\delta^{0}}{\sigma^{2}}$ (85) $\displaystyle\phi_{0}$
$\displaystyle=$
$\displaystyle\phi_{0}^{0}-V_{23}\frac{\delta^{0}}{\sigma^{2}}$ (86)
$\displaystyle\delta$ $\displaystyle=$
$\displaystyle\delta^{0}-V_{33}\frac{\delta^{0}}{\sigma^{2}}$ (87)

where $g_{ij}$ is the identity matrix (1 if $i=j$, 0 otherwise).

###  5.2 SZ plane

The solution in this case is:

$\displaystyle W_{ij}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}T_{11}^{0}+\frac{s^{2}}{\sigma^{2}},&T_{12}^{0}+\frac{s}{\sigma^{2}}\\\
T_{21}^{0}+\frac{s}{\sigma^{2}},&T_{22}^{0}+\frac{1}{\sigma^{2}}\\\
\end{array}\right)^{-1}$ $\displaystyle\Downarrow$ $\displaystyle\tan\lambda$
$\displaystyle=$
$\displaystyle\tan\lambda^{0}-(W_{11}~{}s+W_{12})~{}\frac{z_{0}^{0}+s\tan\lambda-
z_{meas}}{\sigma^{2}}$ (91) $\displaystyle z_{0}$ $\displaystyle=$
$\displaystyle z_{0}^{0}-(W_{21}~{}s+W_{22})~{}\frac{z_{0}^{0}+s\tan\lambda-
z_{meas}}{\sigma^{2}}$ (92)

where $\tan\lambda^{0}$ and $z_{0}^{0}$ are the original SZ parameters of the
track, $\sigma_{z}$ is the uncertainty on $z_{meas}$, $s$ is the arc length
described in the XY plane and $T_{ij}^{0}$ is the inverse of $W_{ij}^{0}$, the
original covariance matrix in the SZ plane.

###  5.3 Constraining a track to a point

Sometimes we are not interested in a precise estimate of the uncertainties
when a new measurement is added to a track, but only in the improvements
obtained in the limit in which this measurement is much more precise than the
uncertainty of the track extrapolation to it, i.e. the limit in which a track
is constrained to a point. We will denote the new measurement by
$(x_{fix},y_{fix},z_{fix})$. In this case the equations presented in the
previous section can be largely simplified.

In the system in which the fixed point is the reference point, the solution
for the XY plane when $\sigma\rightarrow 0$ is:

$\displaystyle C$ $\displaystyle=$ $\displaystyle
C^{0}-\frac{V_{13}^{0}}{V_{33}^{0}}~{}\delta^{0}$ (93) $\displaystyle\phi_{0}$
$\displaystyle=$
$\displaystyle\phi_{0}^{0}-\frac{V_{23}^{0}}{V_{33}^{0}}~{}\delta^{0}$ (94)
$\displaystyle\delta$ $\displaystyle=$ $\displaystyle 0$ (95)

and a convenient parametrization of the covariance matrix in this limit is:

$\displaystyle V_{ij}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{ccc}\frac{S_{22}^{0}}{S_{11}^{0}S_{22}^{0}-S_{12}^{0}S_{12}^{0}}&\frac{-S_{12}^{0}}{S_{11}^{0}S_{22}^{0}-S_{12}^{0}S_{12}^{0}}&0\\\
\frac{-S_{12}^{0}}{S_{11}^{0}S_{22}^{0}-S_{12}^{0}S_{12}^{0}}&\frac{S_{11}^{0}}{S_{11}^{0}S_{22}^{0}-S_{12}^{0}S_{12}^{0}}&0\\\
0&0&\sigma^{2}\end{array}\right)$ (99)

where the true (but small) value of the uncertainty $\sigma$ must be used to
ensure that the covariance matrix is not singular. In the SZ plane we obtain:

$\displaystyle\tan\lambda$ $\displaystyle=$
$\displaystyle\tan\lambda^{0}-\frac{sW_{11}^{0}+W_{12}^{0}}{s^{2}W_{11}^{0}+2sW_{12}^{0}+W_{22}^{0}}~{}(z_{0}^{0}+s\tan\lambda^{0}-z_{fix})$
(100) $\displaystyle z_{0}$ $\displaystyle=$ $\displaystyle
z_{fix}-s\tan\lambda$ (101)

with a covariance matrix in the $\sigma_{z}\rightarrow 0$ limit given by:

$\displaystyle W_{ij}$ $\displaystyle=$
$\displaystyle\frac{1}{T_{11}^{0}-2sT_{12}^{0}+s^{2}T_{22}^{0}}\left(\begin{array}[]{cc}1+T_{22}^{0}\sigma_{z}^{2},&-s-T_{12}^{0}\sigma_{z}\\\
-s-T_{12}^{0}\sigma_{z}^{2},&s^{2}+T_{11}^{0}\sigma_{z}^{2}\end{array}\right)$
(104)

where again a non-null value of $\sigma_{z}$ is necessary to avoid potential
singularities.

##  6 Common vertex for several tracks in XY

Finding the common vertex for several tracks (at least 2) in the XY plane is
equivalent to finding a new common reference point,
$(x_{r}^{\prime},y_{r}^{\prime})$ that globally minimizes the distances of
closest approach of all those tracks. We address the problem using Equation 24
as starting point:

$\displaystyle\delta^{\prime}_{i}=\delta_{i}-\frac{C_{i}\delta^{2}_{i}}{2}+\left(\Delta_{x}\sin\phi_{0i}-\Delta_{y}\cos\phi_{0i}\right)~{}(1-C_{i}\delta_{i})-C_{i}~{}\frac{\Delta_{x}^{2}+\Delta_{y}^{2}}{2}$
(105)

where $\delta^{\prime}_{i}$ is the distance of closest approach of the $ith$
track to the common vertex $(x_{r}^{\prime},y_{r}^{\prime})$. For convenience
we choose to determine the parameters $\Delta_{x}$ and $\Delta_{y}$, which are
the coordinates of the vector that connects the initial and final reference
points:
$(\Delta_{x},\Delta_{y})\equiv(x_{r}^{\prime}-x_{r},y_{r}^{\prime}-y_{r})$.
Explicitly, the $\chi^{2}$ to be minimized is:

$\displaystyle\chi_{xy}^{2}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\left(\frac{\delta^{\prime}_{i}}{\sigma_{i}}\right)^{2}$
(106)

where $\sigma_{i}$ is the error the distance of closest approach for the $ith$
track.

The safest way to find the solution in terms of $\Delta_{x}$ and $\Delta_{y}$
the use standard minimization programs like Minuit [14]. Nevertheless, if the
initial reference point $(x_{r},y_{r})$ is expected to be close to the final
vertex, the solution can be found by iteration using a Newton minimization
method. The method is expected to converge as long as
$C_{i}~{}(\Delta_{x}^{2}+\Delta_{y}^{2})$ terms stay small in the process.
This is typically the case of the determination of the primary vertex of the
event, where the initial reference can be well approximated by a nominal
collision vertex position and the number of tracks is sufficiently large to
avoid the presence of far minima. Expanding the $\chi^{2}$ up to terms
quadratic in $\Delta_{x},\Delta_{y}$:

$\displaystyle\alpha_{i}$ $\displaystyle=$
$\displaystyle\frac{2~{}\delta_{i}-C_{i}\delta^{2}_{i}}{2~{}\sigma_{i}}$ (107)
$\displaystyle\beta_{i}$ $\displaystyle=$
$\displaystyle\frac{\sin\phi_{0i}~{}(1-C_{i}\delta_{i})}{\sigma_{i}}$ (108)
$\displaystyle\gamma_{i}$ $\displaystyle=$
$\displaystyle-\frac{\cos\phi_{0i}~{}(1-C_{i}\delta_{i})}{\sigma_{i}}$
$\displaystyle\downarrow$ $\displaystyle\chi_{xy}^{2}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\biggl{[}\biggr{.}\alpha^{2}_{i}+\left(\begin{array}[]{cc}2\alpha_{i}\beta_{i},2\alpha_{i}\gamma_{i}\end{array}\right)\left(\begin{array}[]{c}\Delta_{x}\\\
\Delta_{y}\end{array}\right)$ (119)
$\displaystyle+\left(\begin{array}[]{cc}\Delta_{x},&\Delta_{y}\end{array}\right)~{}\left(\begin{array}[]{cc}\beta^{2}_{i}-C_{i}\alpha_{i}&\beta_{i}\gamma_{i}\\\
\beta_{i}\gamma_{i}&\gamma^{2}_{i}-C_{i}\alpha_{i}\end{array}\right)~{}\left(\begin{array}[]{c}\Delta_{x}\\\
\Delta_{y}\end{array}\right)+\ldots\biggl{.}\biggr{]}$

The minimization of the quadratically truncated $\chi^{2}$ leads to the
solution:

$\displaystyle\left(\begin{array}[]{c}\Delta_{x}\\\
\Delta_{y}\end{array}\right)$ $\displaystyle=$
$\displaystyle-~{}\left(\begin{array}[]{cc}\beta^{2}_{i}-C_{i}\alpha_{i}&\beta_{i}\gamma_{i}\\\
\beta_{i}\gamma_{i}&\gamma^{2}_{i}-C_{i}\alpha_{i}\end{array}\right)^{-1}~{}\left(\begin{array}[]{c}\sum\alpha_{i}\beta_{i}\\\
\sum\alpha_{i}\gamma_{i}\end{array}\right)$ (126)

This Newton step must be iterated until the vertex converges to a stable
value. The minimization can be stopped for instance when the distance between
the vertices of two consecutive iterations becomes of the order of the average
impact parameter uncertainty: $\approx(\sum 1/\sigma_{i}^{2})^{-1/2}$. Note
that, in each iteration, the reference point is the vertex estimated in the
previous iteration. Accordingly, the parameters $\phi_{0i}$ and $\delta_{i}$
will have to be propagated to the new reference point using Equations 19 and
20 before the iteration starts. Let us point out that, if convenient, the
parameters of the tracks used in the vertex determination can be further
improved a posteriori by constraining them to the common vertex 444In
principle there is a remaining correlation effect between each track parameter
and the common vertex position, which should be taken into account. However,
this correlation is expected to be small as long as the total number of tracks
is sufficiently large., using the equations developed in Section 5.

##  7 Common vertex for several tracks in space

The $\chi^{2}$ contribution in the SZ plane is:

$\displaystyle\chi_{z}^{2}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\left(\frac{\Delta_{Z}-z_{0i}-\frac{\tan\lambda_{i}}{\mathrm{sinc}(C_{i}s_{i})}~{}(\Delta_{x}\cos\phi_{0i}+\Delta_{y}\sin\phi_{0i})}{\sigma_{zi}}\right)^{2}$
(127)

where $s_{i}$ is the arc length from a displacement given by
$(\Delta_{x},\Delta_{y})$ and $\sigma_{zi}$ is the uncertainty on $z_{0i}$.
Note that, due to the convention used in the parametrization, $\Delta_{Z}$ is
not a distance with respect to the reference point, but with respect to $z=0$.
Again, $C\delta^{\prime}$ terms are neglected. The global $\chi^{2}$ to be
minimized is:

$\displaystyle\chi^{2}=\chi_{xy}^{2}+\chi_{sz}^{2}\;,$ (128)

which can be easily solved for $(\Delta_{x},\Delta_{y},\Delta_{z})$ using
standard minimization programs. Similarly to the $XY$ case, one can also try a
Newton minimization procedure if the common vertex is not expected to be far
from the initial reference point. In this 3D case, the solution of the
quadratically truncated $\chi^{2}$ at each minimization step can be obtained
from the following definitions:

$\displaystyle\alpha_{i}$ $\displaystyle=$
$\displaystyle\frac{2\delta_{i}-C_{i}\delta^{2}_{i}}{2\sigma_{i}}$ (129)
$\displaystyle\beta_{i}$ $\displaystyle=$
$\displaystyle\frac{\sin\phi_{0i}~{}(1-C_{i}\delta_{i})}{\sigma_{i}}$ (130)
$\displaystyle\gamma_{i}$ $\displaystyle=$
$\displaystyle-\frac{\cos\phi_{0i}~{}(1-C_{i}\delta_{i})}{\sigma_{i}}$ (131)
$\displaystyle\xi_{i}$ $\displaystyle=$
$\displaystyle\frac{\cos\phi_{0i}\tan\lambda_{i}}{\mathrm{sinc}(C_{i}s_{i})~{}\sigma_{zi}}$
(132) $\displaystyle\eta_{i}$ $\displaystyle=$
$\displaystyle\frac{\sin\phi_{0i}\tan\lambda_{i}}{\mathrm{sinc}(C_{i}s_{i})~{}\sigma_{zi}}$
(133) $\displaystyle W_{\Delta x\Delta y\Delta z}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{ccc}\sum(\beta_{i}^{2}+\xi_{i}^{2}-C_{i}\alpha_{i})&\sum(\beta_{i}\gamma_{i}+\xi_{i}\eta_{i})&-\sum\frac{\xi_{i}}{\sigma_{zi}}\\\
&&\\\
\sum(\beta_{i}\gamma_{i}+\xi_{i}\eta_{i})&\sum(\gamma_{i}^{2}+\eta_{i}^{2}-C_{i}\alpha_{i})&-\sum\frac{\eta_{i}}{\sigma_{zi}}\\\
&&\\\
-\sum\frac{\xi_{i}}{\sigma_{zi}}&-\sum\frac{\eta_{i}}{\sigma_{zi}}&\sum\frac{1}{\sigma_{zi}^{2}}\end{array}\right)^{-1}\;,$
(139)

leading to the solution:

$\displaystyle\left(\begin{array}[]{c}\Delta_{x}\\\ \Delta_{y}\\\
\Delta_{z}\end{array}\right)$ $\displaystyle=$ $\displaystyle-W_{\Delta
x\Delta y\Delta
z}~{}\left(\begin{array}[]{c}\sum(\alpha_{i}\beta_{i}+z_{0i}\frac{\xi_{i}}{\sigma_{zi}})\\\
\\\ \sum(\alpha_{i}\gamma_{i}+z_{0i}\frac{\eta_{i}}{\sigma_{zi}})\\\ \\\
-\sum\frac{z_{0i}}{\sigma_{zi}^{2}}\end{array}\right)$ (148)

Beside $\phi_{0i}$ and $\delta_{i}$, now also $s_{i}$ will have to be
propagated to the estimated vertex from $\chi^{2}$ truncation before starting
a new iteration. This can be done using Equations 13 or 14.

## References

  * [1] J. Alcaraz Maestre, Helicoidal tracks, L1 Internal Note 1666, 1994, https://cern.ch/l3/note/notes1994.html.
  * [2] L3, B. Adeva et al., The Construction of the L3 Experiment, Nucl. Instrum. Meth. A 289 (1990) 35–102.
  * [3] L3 SMD, M. Acciarri et al., The L3 silicon microvertex detector, Nucl. Instrum. Meth. A 351 (1994) 300–312.
  * [4] F. Beissel et al., Construction and performance of the L3 central tracking detector, Nucl. Instrum. Meth. A 332 (1993) 33–55.
  * [5] R. Fruhwirth, Application of Kalman filtering to track and vertex fitting, Nucl. Instrum. Meth. A 262 (1987) 444–450.
  * [6] J. C. Hart and D. H. Saxon, Track and Vertex Fitting in an Inhomogeneous Magnetic Field, Nucl. Instrum. Meth. A 220 (1984) 309–326.
  * [7] J. Alcaraz, Track fitting in slightly inhomogeneous magnetic fields, Nucl. Instrum. Meth. A 553 (2005) 613–619, arXiv:physics/0507129.
  * [8] CMS, S. Chatrchyan et al., The CMS Experiment at the CERN LHC, JINST 3 (2008) S08004.
  * [9] P. Billoir and S. Qian, Fast vertex fitting with a local parametrization of tracks, Nucl. Instrum. Meth. A 311 (1992) 139–150.
  * [10] A. Salzburger, Track Simulation and Reconstruction in the ATLAS experiment, PhD thesis, Innsbruck U., 2008, http://cds.cern.ch/record/2224514.
  * [11] ATLAS, G. Aad et al., The ATLAS Experiment at the CERN Large Hadron Collider, JINST 3 (2008) S08003.
  * [12] V. Innocente, M. Maire, and E. Nagy, GEANE: Average tracking and error propagation package, in Workshop on Detector and Event Simulation in High-energy Physics (MC ’91), pp. 58–78, 1991, https://cds.cern.ch/record/247710.
  * [13] V. Karimaki, Effective circle fitting for particle trajectories, Nucl. Instrum. Meth. A 305 (1991) 187–191.
  * [14] F. a. James, MINUIT: Function Minimization and Error Analysis Reference Manual, https://cds.cern.ch/record/2296388, CERN Program Library Long Writeups.

## Appendix A. Alternative track parametrizations.

Here we collect the Jacobians
$J\left(\frac{\partial(\mathrm{new~{}parameters})}{\partial(C,\phi_{0},\delta,\tan\lambda,z_{0})}\right)$
for the alternative parametrizations discussed in subsection 2.1:

  * •

Perigee parametrization [9]:

$\displaystyle\rho$ $\displaystyle\equiv$ $\displaystyle-C$ (149)
$\displaystyle\phi_{p}$ $\displaystyle\equiv$ $\displaystyle\phi_{0}$ (150)
$\displaystyle\epsilon$ $\displaystyle\equiv$ $\displaystyle-\delta$ (151)
$\displaystyle\theta$ $\displaystyle\equiv$
$\displaystyle\frac{\pi}{2}-\lambda$ (152) $\displaystyle z_{p}$
$\displaystyle\equiv$ $\displaystyle z_{0}$ (153)

$\displaystyle
J\left(\frac{\partial(\rho,\phi_{p},\epsilon,\theta,z_{p})}{\partial(C,\phi_{0},\delta,\tan\lambda,z_{0})}\right)=\left(\begin{array}[]{c|c|c|c|c}-1&0&0&0&0\\\
\hline\cr 0&1&0&0&0\\\ \hline\cr 0&0&-1&0&0\\\ \hline\cr
0&0&0&-\cos^{2}\lambda&0\\\ \hline\cr 0&0&0&0&1\end{array}\right)$ (159)

  * •

Modified perigee parametrization [10]:

$\displaystyle\frac{q}{p}$ $\displaystyle\equiv$
$\displaystyle\frac{C\cos\lambda}{0.29979~{}B}$ (160) $\displaystyle\phi_{p}$
$\displaystyle\equiv$ $\displaystyle\phi_{0}$ (161) $\displaystyle\epsilon$
$\displaystyle\equiv$ $\displaystyle-\delta$ (162) $\displaystyle\theta$
$\displaystyle\equiv$ $\displaystyle\frac{\pi}{2}-\lambda$ (163)
$\displaystyle z_{p}$ $\displaystyle\equiv$ $\displaystyle z_{0}$ (164)

$\displaystyle
J\left(\frac{\partial(q/p,\phi_{p},\epsilon,\theta,z_{p})}{\partial(C,\phi_{0},\delta,\tan\lambda,z_{0})}\right)=\left(\begin{array}[]{c|c|c|c|c}\frac{\cos\lambda}{0.29979~{}B}&0&0&-\frac{C\sin\lambda\cos^{2}\lambda}{0.29979~{}B}&0\\\
\hline\cr 0&1&0&0&0\\\ \hline\cr 0&0&-1&0&0\\\ \hline\cr
0&0&0&-\cos^{2}\lambda&0\\\ \hline\cr 0&0&0&0&1\end{array}\right)$ (170)

  * •

Curvilinear parametrization at the minimum distance of transverse approach
[12]:

$\displaystyle\frac{q}{p}$ $\displaystyle\equiv$
$\displaystyle\frac{C\cos\lambda}{0.29979~{}B}$ (171) $\displaystyle\phi$
$\displaystyle\equiv$ $\displaystyle\phi_{0}$ (172) $\displaystyle x_{\perp}$
$\displaystyle\equiv$ $\displaystyle\delta$ (173) $\displaystyle\lambda$
unchanged (174) $\displaystyle z_{\perp}$ $\displaystyle\equiv$ $\displaystyle
z_{0}~{}\cos\lambda$ (175)

$\displaystyle
J\left(\frac{\partial(q/p,\phi,x_{\perp},\lambda,z_{\perp})}{\partial(C,\phi_{0},\delta,\tan\lambda,z_{0})}\right)=\left(\begin{array}[]{c|c|c|c|c}\frac{\cos\lambda}{0.29979~{}B}&0&0&-\frac{C\sin\lambda\cos^{2}\lambda}{0.29979~{}B}&0\\\
\hline\cr 0&1&0&0&0\\\ \hline\cr 0&0&1&0&0\\\ \hline\cr
0&0&0&-\cos^{2}\lambda&0\\\ \hline\cr
0&0&0&-z_{0}\sin\lambda\cos^{2}\lambda&\cos\lambda\end{array}\right)$ (181)


# I Tag, You Tag, Everybody Tags!

Hazem Ibrahim  New York University Abu DhabiAbu DhabiUAE<EMAIL_ADDRESS>,  Rohail Asim  New York University Abu DhabiAbu DhabiUAE<EMAIL_ADDRESS>,  Matteo Varvello  Nokia, Bell LabsNew JerseyUSA<EMAIL_ADDRESS>and  Yasir Zaki  New York University Abu DhabiAbu DhabiUAE<EMAIL_ADDRESS>
###### Abstract.

Location tags are designed to track personal belongings. Nevertheless, there
has been anecdotal evidence that location tags are also misused to stalk
people. Tracking is achieved locally, e.g., via Bluetooth with a paired phone,
and remotely, by piggybacking on location-reporting devices which come into
proximity of a tag. This paper studies the performance of the two most popular
location tags (Apple’s AirTag and Samsung’s SmartTag) through controlled
experiments – with a known large distribution of location-reporting devices –
as well as in-the-wild experiments – with no control on the number and kind of
reporting devices encountered, thus emulating real-life use-cases. We find
that both tags achieve similar performance, e.g., they are located 55% of the
times in about 10 minutes within a 100 m radius. It follows that real time
stalking to a precise location via location tags is impractical, even when
both tags are concurrently deployed which achieves comparable accuracy in half
the time. Nevertheless, half of a victim’s exact movements can be backtracked
accurately (10m error) with just a one-hour delay, which is still perilous
information in the possession of a stalker.

##  1\. Introduction

Location tags such as AirTag (Apple) and SmartTag (Samsung) enable the
monitoring of the location of any object they are attached to. This is
achieved locally by using Bluetooth Low Energy (BLE) – or using Ultra Wideband
if supported – between a tag and the device it is paired with. When the
location tag is out of reach, location updates are provided remotely by
piggybacking on any compatible iOS device, such as iPhones and iPads (for
AirTag), or Samsung Galaxy devices (for SmartTag) which come into proximity of
such tag. For a device to be location-reporting, i.e., eligible to relay a
tag’s location, it must support location finding, which Apple enables by
default, but must be opted in on Samsung devices.

Although the intended use case of tags is locating objects, there is anecdotal
evidence of their misuse for tracking people (Dyer, 2022; Levitt, 2022) or
stalking. To the best of our knowledge, no scientific study has yet quantified
the accuracy of location tags in the wild, which directly correlates with
their ability (or not) to act as stalking devices. Their efficacy in both
locating and/or stalking depends on a few factors: 1) the technology adopted,
and 2) the probability of encountering a location-reporting device, e.g., a
Samsung or Apple with enabled Bluetooth, GPS location, and data connectivity.
While the reach of the technology can be studied in a lab, the opportunistic
encountering of a reporting device requires experiments in the wild to account
for realistic conditions.

The goal of this paper us to study the performance of location tags. We tackle
this problem with both controlled and in-the-wild experiments. To enable such
experiments, we develop crawlers for each tag’s companion app (FindMy and
SmartThings) which collect fine-grained tags location histories as reported by
location-reporting devices. We use controlled experiments to shed some light
on the behavior of location tags, e.g., how frequently their location is
reported. First, we deploy an AirTag and a SmartTag in a secluded area along
with Samsung and Apple devices at increasing distance. Next, we deploy both
tags in our campus cafeteria whose WiFi provides us an estimate of the number
of Apple and Samsung devices present at any point in time.

We use experiments in the wild to comment on the effectiveness of their
opportunistic location reporting in various scenarios, e.g., user mobility,
population densities, times of day, and days of the week. We rely on four
volunteers to carry an AirTag (Apple) and SmartTag (Samsung) while traveling
to six different countries. The tags are mounted on the cover of an Android
phone – not paired with the tags, and not an Apple or Samsung – which is
equipped with a custom app logging information like GPS location,
connectivity, etc. The data collected spans 120 days, and 9,378 Kms traveled
across 20 cities.

Our analysis shows that AirTag and SmartTag achieve similar performance with
respect to how quickly and precisely they can be located. Despite the lower
probability to encounter Samsung location-reporting devices, SmartTag matches
AirTag performance by adopting a more aggressive strategy of higher power
Bluetooth beacons – which are received further away but require 20% more
battery usage – and more frequent location reports. Overall, 10 minutes are
needed to locate a tag within 100 m from its true location, even when
emulating a scenario where Apple devices can report SmartTags’ location and
vice-versa. This result implies that a victim’s precise location can rarely be
tracked in real time, even when both tags are concurrently deployed. Still,
half of a victim’s movements can be retraced with a 10 meters accuracy after
just one hour, which is still dangerous information in the hand of a stalker.
Furthermore, such stalking capability is achieved with minimal cost ($30 per
tag) and for a very long time, given that both devices guarantee a battery
life of about one year.

##  2\. Background and Related Work

Location tags like AirTag (Apple) and SmartTag (Samsung) use the Bluetooth Low
Energy (BLE) (Heydon and Hunn, 2012) protocol to transmit a unique identifier
with a range of up to 100 meters. SmartTag+ and the AirTag also support Ultra
Wideband (Sahinoglu et al., 2008) which further extends the range while
allowing more precise device localization. Ultra Wideband is only supported by
recent devices, such as iPhone models $\geq$ 11, and Samsung Galaxy from the
S21 onwards.

In addition to local (Bluetooth) tracking, remote tracking is achieved by
allowing location-reporting devices – iOS devices for AirTags, Samsung devices
for SmartTags – to report the location of tags encountered in the wild.
Whenever a location-reporting device comes in the proximity of a location tag,
i.e., it receives a Bluetooth beacon, it updates the tag’s location in the
cloud using its GPS coordinates as an approximation. Tag owners can check
their location via the tag’s companion application. This process is private,
without leaking any information about either the tag’s owner or the device
which has reported its last location.

Apple and Samsung have implemented measures to deter malicious tracking, yet
these measures have been insufficient, as discussed in (Heinrich et al.,
2021). In addition, each vendor only alerts a user if an unpaired tag from the
same vendor has been in their vicinity for an extended period of time. This
means that an AirTag could be used to stalk Samsung users and vice-versa. To
address this, Apple released “Tracker Detect” (Apple, 2022) an Android
application which allows its users to manually scan for nearby AirTags.
Heinrich et al. (Heinrich et al., 2022) improved this design by automatically
alerting users if they encounter the same AirTag in three separate locations
within a 24 hour period. Similarly, Briggs et al. (Briggs and Geeng, 2022)
extend the design proposed by Heinrich et al. to generic tags, not just
AirTags. These applications are only partially effective due to MAC address
randomization (Apple, 2021), which makes tags eventually appear as new devices
to a third-party app. Mayberry et al. (Mayberry et al., 2021) developed a
custom location tag which mimics an AirTag, can be tracked in Apple’s FindMy
network, and can circumvent Apple’s tracking of malicious AirTags. Last but
not least, Shaqfat et al. (Shafqat et al., 2023) also demonstrate that the
security measures implemented by Apple can be circumvented with a custom
location tag, and suggest solutions to mitigate stalking risks from cloned
AirTags and enhance the existing anti-stalking safeguards for AirTags.

To the best of our knowledge, no previous paper investigates the performance
(i.e., accuracy and responsiveness) of tags in real-world scenarios on a
global scale. Instead, Givehchian et al. (Givehchian et al., 2022) have
investigated the privacy of devices using the BLE protocol, such as location
tags, showing that physical-layer identification is viable although often
unreliable. Hernández et al. (Hernández-Orallo et al., 2023) have studied the
efficiency of finding AirTags and Tile tags on a university campus through
real and simulated experiments, where they model the probability of locating a
tag utilizing the flow rate of individuals carrying a compatible smartphone in
the tag’s detection range. They showed that AirTags exhibit a range between
10-30 m (inline with our own findings). Furthermore, their results indicate
that given a populated area, both tags relayed their location within one hour
98% of the time. Our work differs from the work of (Hernández-Orallo et al.,
2023) in that we expand our analysis to a global scale, analyzing the
efficiency of AirTags and SmartTags across multiple countries. Moreover, we
enhance their real experiments with a more comprehensive controlled experiment
to evaluate the relationship between smartphone density and location update
rate.

Figure 1. On the left, two data collection servers (MacOS and Ubuntu) run the
FindMy and SmartThings crawlers. On the right, several views of our vantage
point, a Redmi Go equipped with two tags.

##  3\. Methodology

This section outlines the methodology we have devised to evaluate location
tags. While we focus on AirTag (Apple) and SmartTag (Samsung), the methodology
is generic and can be adopted to study other location tags like Tile (Tile,
2023).

###  3.1. Location Tags Pairing

Apple AirTag: This tag must be paired and registered via Bluetooth with an iOS
or iPadOS device above version 14.5, i.e., no MacOS. Once the tag is linked to
the Apple ID of the device it is paired with, it is then displayed in the
FindMy app across all devices that have signed in with that Apple ID
(including MacOS devices).

Samsung SmartTag: This tag can only be paired and registered via Bluetooth
with a Samsung Galaxy device running Android $\geq$8.0. The tag is linked to
the Samsung account of the registered device, and it is displayed as a linked
device in Samsung SmartThings app.

###  3.2. Tag Data Collection

At the time when we developed our methodology, neither Samsung nor Apple
offered public APIs to access tag’s location data ($<$timestamp, GPS
location$>$) as maintained by each tag’s companion app: FindMy (Apple) and
SmartThings (Samsung). In addition, FindMy did not support location history,
and SmartThings only provided some low resolution location history for up to 6
days. Therefore, we developed “crawlers” for both apps which monitor location
changes once a minute, and can thus build fine-grained location histories.
Recently, Apple has released an API to allow authenticated users to query the
FindMy service and retrieve location reports, as discussed in (Bellon et al.,
2023).

FindMy Crawler: The FindMy app is available for Apple devices, e.g., Macbook,
iPhone, and iPad. For ease of instrumentation, we write a crawler for MacOS.
Note that MacOS v11 or above is needed, since FindMy on older MacOS does not
support AirTags. In FindMy, users can find the last reported coordinates of
any paired AirTag as follows. First, by clicking on the targeted tag from the
list of devices in FindMy and selecting the option to open the location in
Apple Maps. Once Apple Maps is launched, a pin is placed with the latest
reported location of the tag. With a right-click, the user is given the option
to “copy coordinates”. We wrote a FindMy crawler in Python using pyautogui
(PyAutoGui, 2019) to automate the above, and store the last reported
coordinates of each available AirTag. Along with a tag’s coordinates, we also
store a timestamp approximating when the coordinates were reported. This is
computed using the crawling epoch time and the time at which a tag was last
seen which is reported by FindMy as “X minutes ago”, thus adding a potential
error of up to one minute. Given this “last seen” time cannot be extracted
from the FindMy app, we use OCR (Mori et al., 1999) to convert its value into
text.

SmartThings Crawler: The SmartThings app is only available for Android. In the
app, users select a tag from the list of tags associated with their account,
and then click “view location” which opens Google Maps with a pin showing the
tag’s location. At this point, the tag’s coordinates are available in the
search bar and can be copied. We automate SmartThings via the Android
Debugging Bridge (ADB (Google, 2023)), a rich Android protocol which allows to
automate app operations like launching, scrolling, and GUI interaction. We
connect an Android device, previously paired with one or more SmartTags, to a
Linux machine via USB. ADB is then used to launch SmartThings and iterate over
the tags. Once a tag’s coordinates are available in Google Maps, they are
copied and logged to a file. The same OCR-based procedure described for FindMy
is used to approximate the time at which the tag location was updated last.

###  3.3. Vantage Point

A vantage point consists of an Android device (Xiaomi Redmi Go with a 1.4 GHz
Quad-core and a 1 GB RAM), an AirTag and a SmartTag; both tags are mounted on
a custom cover for the mobile device which we designed and 3D printed as part
of the AmiGo testbed (Varvello and Zaki, 2023) (see Figure 1). The tags are
paired with testing Samsung and Apple accounts as described in Section 3.1.
Note that the Android device used is not capable of reporting the location of
neither tags, thus not impacting the accuracy of the experiments.

The Android device is equipped with an app we developed which collects GPS
data, if available. The app buffers pairs of $<$timestamp, GPS location$>$
with a 5-second frequency for up to five minutes; only GPS variations are
recorded, thus avoiding redundant data. After five minutes, the buffered data
is POSTed to a server in our lab, if a data connection is available.
Otherwise, the data is kept in the buffer until a connection becomes
eventually available. The $<$timestamp, GPS location$>$ pairs are used as the
ground truth of where the tags were located at a given point in time. This
allows us to evaluate the accuracy of a tag’s location as shown by its
companion app, i.e., as reported by location-reporting devices
opportunistically encountered by location tags.

Ctry | # of | # Report | # Report | Walk/Jog/ | Days
---|---|---|---|---|---
| cities | Samsung | Apple | Transit(km) |
US | 2 | 145 | 4,821 | 14/22/871 | 30
IT | 10 | 1,361 | 4,520 | 157/68/3,170 | 28
AE | 2 | 1,442 | 9,572 | 145/151/3,384 | 52
PK | 1 | 129 | 454 | 13/16/165 | 2
CH | 1 | 331 | 489 | 14/16/62 | 3
DE | 4 | 187 | 1,225 | 46/45/1,021 | 5
Tot. | 20 | 3,595 | 21,081 | 388/317/8,673 | 120
Table 1. Summary of data-set collected in the wild. # Report refer to the
number of times that tag locations were reported as “Now” in each companion
app. Figure 2. Beacon RSSI for each tag at different distances. Figure 3.
Update rates of AirTag and SmartTag at different times of day in a busy
university cafeteria. Figure 4. AirTag/SmartTag update rates as a function of
the likelihood to have N reporting devices within one hour.

##  4\. Data Collection and Analysis

This section describes two data-sets (controlled and in-the-wild) we have
collected. It further details the crawling infrastructure used. Lastly, it
introduces metrics and methodology we have devised to analyze location tag
data-sets

Controlled Experiments – We deployed an AirTag and a SmartTag at a university
cafeteria over five days. The cafeteria serves roughly 1,000 students,
faculty, and staff, and operates everyday between 7:30am and 10pm, with peak
hours during lunch (12 to 3pm) and dinner (6 to 9pm). Meanwhile, we ran our
crawlers and collaborated with the university’s IT infrastructure team to
monitor the number of Apple and Samsung devices connected to the WiFi access
point in the cafeteria. This is achieved by inspecting the destinations of the
traffic generated by each device connected to WiFi. The rationale is that a
clear distinction arises between Samsung and Apple devices since they rely on
disjoint and proprietary data-centers to run their services. This was needed
as modern mobile phones hide their vendor information from the MAC address
(Apple, 2021). This information was aggregated into a count of the number of
Apple and Samsung devices at different times, and thus completely anonymized.

One limitation of this experiment is that we miss devices not connected to
WiFi. While we cannot quantify this limitation, most phones rely on WiFi due
to poor mobile coverage in the cafeteria. Another limitation is that we
approximate the number of devices connected to WiFi to the number of reporting
devices. This can be an overestimate, especially for Samsung devices whose
users are required to opt-in to enable this behavior.

We conduct an experiment in a secluded area – 300 m away from any building –
where only our tags and phones are present. For each tag, we deploy four
phones at distances of 0, 10, 20, and 50 m from the tag and measure both the
frequency and strength of the Bluetooth beacons received. SmartTags beacons
are easy to detect as they carry the sending tag name. Note that AirTags
beacons can be uniquely identified since they share the first 4 bytes of their
header (“1EFF004C12”).

In-The-Wild Experiments – We deployed four vantage points (Android device
reporting GPS location along with an AirTag and a SmartTag) via four
volunteers between March and August 2022. In total, the tags were carried
along 9,378 Kms across six countries and 20 cities (see Table 1). Participants
were instructed to carry the vantage point as much as possible, and only
interact with it to charge the phone, connect to WiFi, or insert a SIM card
with a mobile data plan. To avoid biasing results in favor of either tag,
participants ensured the location reporting option was disabled on any
personal device they owned. Other family members were not required to do so.
We filter data recorded within a 300 m radius of each participant’s home, as
to not bias the data in the event of a neighbor or family member’s phone
repeatedly reporting a tag’s location. Home locations are assumed as our
participants homes, hotels, or any place they slept overnight. Overall, this
filter accounted for 65% of all data collected.

Figure 5. Evaluation of AirTag, SmartTag and “combined” accuracy in the wild.
(a) Time sweep (10 m radius). (b) Time sweep (25 m radius). (c) Time sweep
(100 m radius). (d) Diff. speeds in a 10 min bucket. (e) Day times in a 10 min
bucket. (f) Week days in a 10 min bucket.

We analyze the performance of AirTag and SmartTag both independently and
combined, which emulates a scenario where both devices report the location of
each other’s tags, functionally detaching the two tags from their proprietary
ecosystems. This scenario is representative of a victim being stalked by both
tags concurrently. We rely on two metrics: accuracy and responsiveness.

Accuracy – At high level, assessing the accuracy of a tag consists of
comparing its reported location, at a given time, with the location of its
associated vantage point. Several factors might impact a tag’s accuracy. First
and foremost, the tag’s location is approximated by the GPS location of the
reporting device. Given Bluetooth has a 100 meter range, this can cause an
error of up to 100 m. Another source of error is the movement of both the tag
and the reporting device: as these devices move, the time needed to extract
and report the GPS location can introduce some error. For example, when moving
on a high speed train (300 Kmh) our sampling of the GPS locations every 5 s
can introduce an error of up to 400 m.

For a given tag, we group the locations reported within the same X-minutes
interval into the same “bucket”. For each X-minutes “bucket”, we calculate the
distance between the location reported by the vantage point and the locations
crawled from the tag’s companion app. If the distance between the vantage
point’s location and a tag’s location is below a (radius) threshold we count a
“hit”, otherwise we count a “miss”. We compute a tag’s accuracy as percentage
of hits. To identify the radii of interest, we analyzed the combined accuracy
of the location tags as we increase the radius of reporting across different
time intervals (see Figure 8 in Appendix C). In the case of short time
intervals (1 and 10 minutes), the accuracy increases as the radius increases,
eventually plateauing at roughly 100 m. For longer time intervals, there is no
significant improvement in accuracy beyond 50 m. Accordingly, we will use the
following radii in our analysis: 10, 25, and 100 m.

Responsiveness – Having accurate tag locations is important, but their
locations also need to be reported in a timely manner. If a tag’s location is
updated frequently, then the owner will have less area to backtrack as (s)he
realizes that the “tagged” object was lost. At the same time, a high update
frequency is also an enabler of stalking or unsolicited tracking. We calculate
tag responsiveness as the difference between the timestamp of the first hit –
i.e., when the distance between the vantage point and a tag’s location is
below a radius — and the first time that the vantage point reported such
location.

Ethics – We obtained IRB approval (HRPP-2021-185) and informed participants of
our data collection practices through a consent form. While we collect GPS
data, we do not gather any identifiable personal information.

##  5\. Results

###  5.1. Controlled

We start by analyzing the signal strength of the Bluetooth beacons emitted by
each tag. To do so, we measure the signal strength in a secluded area with
phones. Figure 2 shows that, at a shorter distances (0 and 10 meters),
SmartTag beacons are received with about 10dBm higher RSSI (Received Signal
Strength Indicator) than AirTag beacons. However, at a distance of 20 meters,
both tags’ beacons were received at a similar RSSI.

Next, we investigate each tag’s update rate, computed as the number of
location updates reported by location-reporting devices every hour.
Accordingly, we focus on the controlled experiments performed in a cafeteria
where the number of Samsung/Apple devices encountered by each tag naturally
varies over time. Figure 3 shows the update rate as a function of the
surrounding location-reporting devices. The figure shows, for each hour of the
day, the average (over 5 days) tag’s update rate and device count, i.e., the
number of Apple and Samsung devices present in the cafeteria. The shaded areas
and error bars in the figure report the standard deviation of each metric. The
figure shows an overall similar update rate between tags, peaking at roughly
15 updates per hour during lunch and dinner, and dipping to zero over night.
However, the figure also shows that there were far more Apple than Samsung
devices, up to 6 times more devices during peak hours, e.g., 320 Apple devices
versus only 50 Samsung devices at 8pm.

To further understand the previous result, Figure 4 shows the update rate as a
function of the likelihood to have N location-reporting devices within one
hour, e.g., up to 10 and between 10 and 20. As expected from Figure 3, it is
more likely to find few Samsung devices, e.g., less than 20, whereas it is
more likely to find lots of Apple devices, e.g., between 100 and 300. The key
result of this analysis is that, while both AirTags and SmartTags converge to
a similar maximum update rate (15-20 updates per hour), they do so in a very
different way. Samsung implements an aggressive update strategy, which quickly
converges to the maximum update rate. In contrast, Apple implements a
conservative strategy, e.g., half the update rate of Samsung when less than 20
devices are present. Samsung’s update rate was not measured beyond 71-80
devices per hour due to the fact that there was never more than 80 Samsung
phones in the cafeteria at any hour during the experiment.

###  5.2. In-The-Wild

Tags Accuracy and Responsiveness – We begin our analysis by investigating each
tag’s accuracy within a given radius as a function of its responsiveness.
Figure 5 summarizes this analysis as we consider a radius of 10, 25, and 100
meters; note that “combined” refers to a unified Apple/Samsung ecosystem.
Intuitively, Figure 5 (a,b,c) shows that relaxing the responsiveness, i.e.,
allowing more time to locate a tag within a radius, improves tag accuracy,
e.g., the combined tag’s accuracy for larger radii (25 and 100 meters) grows
from 10% to 80% as the responsiveness grows from one to 120 minutes. Combining
tags offers a 15% improvement, on average, over the accuracy of each
individual tag.

The previous observations also apply to a small radius (10 meters, see Figure
5a) although with a few important differences. First, one minute is too fast
to locate a tag within such a small radius, e.g., an accuracy of 2% versus
8-10% at larger radii. Second, as we relax the responsiveness, the tag’s
accuracy increases much slower than what is observed for larger radii, e.g.,
40-45% versus 60-63% assuming a responsiveness of 25 minutes. This happens
because, as both tags and reporting users might move, it is more challenging
to correctly report the right location with such small radius and high
responsiveness. Finally, the maximum accuracy caps at 72%, when considering
both tags combined, or 8% less than what observed for larger radii. Given the
slow responsiveness allowed, this reflects errors introduced by approximating
a tag’s location with the reporting device location, which is unlikely more
than 50 meters as per Figure 2.

Finally, if we focus on each tag independently, Figure 5a shows that SmartTag
slightly outperforms AirTag at a radius of 10 m but perform similarly at radii
of 25 and 100 m, which is inline with Samsung’s stronger signal strength at
smaller radii, but similar performance at 20 m as shown in Figure 2.

Mobility and Time of the Day – We continue our analysis by exploring the
effect of different mobility and temporal characteristics on the accuracy of
each tag. For this analysis, we assume a responsiveness of 10 minutes and
radii of 10, 25, and 100 meters. We also compute the statistical significance
between different mobility and temporal scenarios by running t-tests across
the average accuracy computed for each scenario. In Figures 5d-f, statistical
significant tests are denoted using the following symbols: ns denotes a
$p>0.05$, * denotes $0.01<p<0.05$, ** denotes $0.001<p<0.01$, *** denotes
$0.0001<p<0.001$, and **** denotes $p<0.0001$.

Figure 5d shows average tag’s accuracy – 95% confidence intervals reported as
error-bars across the different radii considered – as we vary how fast a tag
is moving (estimated as the average speed over 10 minutes as per our ground
truth). We find that while walking at a pedestrian speed ($<6.0$ km/h), the
accuracy is maximized for both tags and even when combined. The rationale
behind this finding is that walking represents a good equilibrium between
number of devices the tag may be exposed to, e.g., higher than when being
stationary, and the length of the time window for the Bluetooth signal to be
picked up by a location-reporting device. As the speed increases, e.g., when
jogging (speed comprised between $6.0$ and $12.0$ km/h) or in transit ($\geq
12.0$ km/h), the accuracy deteriorates due to the little time allowed for
Bluetooth communication.

Figure 5e shows a tag’s mean accuracy during different times of the day. The
figure shows no significant differences between morning (6 to 10 A.M.) lunch
(10 A.M. and 2 P.M.), afternoon (2 to 6 P.M.) and evening hours (6 to 10
P.M.), but a statistically significant decrease at night (10 P.M. to 2 A.M.).
Next, Figure 5f shows significant tag’s accuracy increase on weekends compared
to weekdays, likely due to greater outdoor activity by the general public.

###  5.3. Discussion

This study highlights the effectiveness of AirTags and SmartTags in tracking
the location of items or individuals across various situations. Specifically,
the findings indicate that while these tags may not provide an immediate
precise location, they can still offer an approximate location with just a one
hour delay. This performance, although not flawless, carries significant
implications for privacy and security, including the potential for misuse such
as government surveillance of dissidents or domestic abuse-related stalking.

It is also important to acknowledge that this study is not without
limitations. While we are able to provide an estimate of the performance of
location tags in real-world scenarios, this performance is ultimately dictated
by the distribution of location-reporting devices in the vicinity of the tags,
which we cannot quantify. Additionally, although our experiments aimed to
encompass a diverse range of real-world scenarios, the study’s scale was
limited, involving only four participants carrying the tags and vantage
points. Future research could expand upon these findings by involving a larger
participant pool and exploring different geographical contexts.

##  6\. Conclusion

Location tags such as AirTag and SmartTag are useful tools for locating
objects, but there is anecdotal evidence of their misuse for tracking and
stalking people. This paper has studied the performance of location tags
through experiments in the wild and in controlled settings; all the data
collected can be found at: https://github.com/comnetsAD/Tags. These
experiments showed that AirTag and SmartTag achieve similar performance with
respect to how quickly and precisely they can be located, in various
scenarios. With respect to “stalking” people, both trackers (or a combination
of the two) can effectively locate half of a victim’s movements with 10 meters
accuracy with just a one-hour delay. Conversely, real time stalking is less
practical given that, most of the time, at least 10 minutes are required to
achieve a 100 meters accuracy. It is important to note that these results
might change over space, e.g., in presence of different distributions of
location reporting devices, and time, e.g., due to future modification of the
reporting protocols.

## References

  * (1)
  * Apple (2021) Apple. 2021.  Wi-Fi privacy - MAC address randomization.  https://support.apple.com/guide/security/wi-fi-privacy-secb9cb3140c/web. (Feb 2021).
  * Apple (2022) Apple. 2022.  Tracker detect - Apple.  https://play.google.com/store/apps/details?id=com.apple.trackerdetect. (Feb 2022).
  * Bellon et al. (2023) Alex Bellon, Alex Yen, and Pat Pannuto. 2023.  TagAlong: Free, Wide-Area Data-Muling and Services. In Proceedings of the 24th International Workshop on Mobile Computing Systems and Applications. 103–109.
  * Briggs and Geeng (2022) Jimmy Briggs and Christine Geeng. 2022.  BLE-Doubt: Smartphone-Based Detection of Malicious Bluetooth Trackers. In 2022 IEEE Security and Privacy Workshops (SPW). IEEE, 208–214.
  * Dyer (2022) James Clayton; Jasmin Dyer. 2022\.  Apple AirTags - ’a perfect tool for stalking’.  https://www.bbc.com/news/technology-60004257. (Jan 2022).
  * Givehchian et al. (2022) Hadi Givehchian, Nishant Bhaskar, Eliana Rodriguez Herrera, Héctor Rodrigo López Soto, Christian Dameff, Dinesh Bharadia, and Aaron Schulman. 2022.  Evaluating physical-layer ble location tracking attacks on mobile devices. In 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 1690–1704.
  * Google (2023) Google. 2023.  Android Debug Bridge.  https://developer.android.com/studio/command-line/adb. (Aug 2023).
  * Heinrich et al. (2022) Alexander Heinrich, Niklas Bittner, and Matthias Hollick. 2022\.  AirGuard-Protecting Android Users from Stalking Attacks by Apple Find My Devices. In Proceedings of the 15th ACM Conference on Security and Privacy in Wireless and Mobile Networks. 26–38.
  * Heinrich et al. (2021) Alexander Heinrich, Milan Stute, Tim Kornhuber, and Matthias Hollick. 2021.  Who can find my devices? security and privacy of apple’s crowd-sourced bluetooth location tracking system.  arXiv preprint arXiv:2103.02282 (2021).
  * Hernández-Orallo et al. (2023) Enrique Hernández-Orallo, Antonio Armero-Martínez, Carlos T Calafate, Pietro Manzoni, et al. 2023\.  Analysis and Evaluation of Tracker Tag Efficiency.  Wireless Communications and Mobile Computing 2023 (2023).
  * Heydon and Hunn (2012) Robin Heydon and Nick Hunn. 2012.  Bluetooth low energy.  CSR Presentation, Bluetooth SIG https://www. bluetooth. org/DocMan/handlers/DownloadDoc. ashx (2012).
  * Kontur (2022) Kontur. 2022.  Kontur Population: Global Population Density for 400m H3 Hexagons.  https://data.humdata.org/dataset/kontur-population-dataset. (Jun 2022).
  * Levitt (2022) Michael Levitt. 2022\.  AirTags are being used to track people and cars. here’s what is being done about it.  https://www.npr.org/2022/02/18/1080944193/apple-airtags-theft-stalking-privacy-tech. (Feb 2022).
  * Mayberry et al. (2021) Travis Mayberry, Ellis Fenske, Dane Brown, Jeremy Martin, Christine Fossaceca, Erik C Rye, Sam Teplov, and Lucas Foppe. 2021\.  Who Tracks the Trackers? Circumventing Apple’s Anti-Tracking Alerts in the Find My Network. In Proceedings of the 20th Workshop on Workshop on Privacy in the Electronic Society. 181–186.
  * Mori et al. (1999) Shunji Mori, Hirobumi Nishida, and Hiromitsu Yamada. 1999\.  Optical character recognition.  John Wiley & Sons, Inc.
  * PyAutoGui (2019) PyAutoGui. 2019\.  Pyautogui’s documentation.  https://pyautogui.readthedocs.io/en/latest/. (Jan 2019).
  * Sahinoglu et al. (2008) Zafer Sahinoglu, Sinan Gezici, and Ismail Guvenc. 2008\.  Ultra-wideband positioning systems.  Cambridge, New York (2008).
  * Shafqat et al. (2023) Narmeen Shafqat, Nicole Gerzon, Maggie Van Nortwick, Victor Sun, Alan Mislove, and Aanjhan Ranganathan. 2023\.  Track You: A Deep Dive into Safety Alerts for Apple AirTags.  Proceedings on Privacy Enhancing Technologies 4 (2023), 132–148.
  * Tile (2023) Tile. 2023.  Tile:Easily find what you can’t live without.  https://www.tile.com/. (Sep 2023).
  * Uber (2018) Uber. 2018.  H3: Uber’s hexagonal hierarchical spatial index.  https://www.uber.com/en-AE/blog/h3/. (Jun 2018).
  * Uber (2023) Uber. 2023.  Tables of cell statistics across resolutions.  https://h3geo.org/docs/core-library/restable/. (Aug 2023).
  * Varvello and Zaki (2023) Matteo Varvello and Yasir Zaki. 2023.  A Worldwide Look Into Mobile Access Networks Through the Eyes of AmiGos. In 2023 7th Network Traffic Measurement and Analysis Conference (TMA). 1–10.  https://doi.org/10.23919/TMA58422.2023.10198920

Figure 6. Visualization of hexagons visited by one of our study participants
over 52 days in Abu Dhabi. Hexagons are derived assuming Uber’s H3 index and a
resolution of 8. The color of each hexagons relates to an estimate of
population density provided by the Kontur data-set.

##  Appendix A Hexagonal Hierarchical Spatial Index

Uber’s Hexagonal Hierarchical Spatial Index (Uber, 2018) models the globe as
an icosahedron, and creates 12 pentagons centered on each of its vertices
joined by 110 hexagons. Each cell is then recursively filled with a number of
hexagons which depends on the desired resolution. The total number of cells at
a given resolution r is given by $c=2+120*7^{r}$. For instance, at a
resolution of zero, the earth is covered by 110 hexagons, whereas at a
resolution of eight, the number of hexagons increases to 691,776,110 (Uber,
2023). Naturally, as the number of cells which cover the surface of the earth
increases, each cells occupies less area overall. At a resolution of eight, an
individual hexagon has an average area of 0.737 km2. In our analysis (see
Section 5.2), we use a resolution of eight as it coincides with the resolution
used in the Kontur Hexagon Population density data set (Kontur, 2022), which
reports population densities within H3 hexagons inferred from satellite images
of building density.

Figure 6 shows an example of the hexagons visited by one of our study
participants in Abu Dhabi (UAE). We consider an hexagon visited if our
participant (and tag) spent at least 5 consecutive minutes within it, thus
ignoring hexagons which a user has only visited briefly, e.g., while driving
on the highway. We color code each hexagon using the Kontur data-set for
population density, from low density (orange) to high density (dark read).
Thresholds for classifying a particular hexagon as low, medium, or high
density are explained in Section 5.2.

Figure 7. CDF of tags accuracy for different population densities; one hour
responsiveness and 100 meters radius.

##  Appendix B Impact of Population Density on Tag Accuracy

Intuitively, the accuracy of a tag depends on the number and type of devices
in their vicinity. While we cannot collect this information in the wild, we
approximate it with the Kontur Hexagon Population density data set (Kontur,
2022), which reports population densities within H3 hexagons inferred from
satellite images of building density. H3 is Uber’s Hexagonal Hierarchical
Spatial Index (Uber, 2018) which groups GPS locations as hexagons.

We group GPS locations from our data-set as hexagons using a “resolution” of
eight as in the Kontur data set; see Appendix A for more details. We threshold
the different population density buckets as the 33rd, 66th, 100th percentiles
of the population densities of all hexagons visited in our study. As such, we
designate hexagons which hold a population $<600$ (33rd percentile) as “low
density”, those with a $600\leq$ population $<1,750$ (66th percentile) as
“medium denisty” and those with population $\geq 1,750$ as “high density”.

Figure 7 shows the Cumulative Distribution Function (CDF) of the accuracy as a
function of population density (low, medium, and high). For this analysis, we
consider a responsiveness of one hour and radius of 100 meters. The figure
shows that the probability of a zero accuracy, i.e., no correct location
reported within 100 meters, drops from 20-25% in low density areas down to
10-15% in high density areas. A slight decrease in accuracy is observed
between low and medium density areas for the median accuracy (roughly 45% in
low-density areas vs. 42% in median-density areas), while it increases to 63%
for high density areas. With respect to the combined accuracy, high density
areas see the least improvement: on average 15% versus 20% in low density
areas. This happens because the benefit of sharing the same ecosystem reduces
as an area is already highly populated with devices from each ecosystem.

Figure 8. Combined accuracy of tags vs. radius across different time windows.

##  Appendix C Impact of Radii on Tag Accuracy

To determine the accuracy of a tag, we compare the vantage point’s location
(our ground truth) with a tag’s location. If this distance is within a radius
we count a “hit”, otherwise we count a “miss”. We then compute a tag’s
accuracy as percentage of hits. To determine which radius values to use in our
analysis, we have explored the impact of different radii on each tag’s
accuracy. Figure 8 shows the combined tag’s accuracy, i.e., considering a
unified Apple/Samsung ecosystem, as a function of both radius and
responsiveness, or how quickly a tag’s location is correctly reported within a
radius value. We only show the combined tag’s accuracy since its trend is
representative of each tag’s accuracy. When considering an aggressive
responsiveness (1 minute), the accuracy greatly improves as the radius
increases, starting with an accuracy of 5% at 10 meters, and increasing to 17%
at 100 meters. When allowed a longer time to correctly locate a tag, the
accuracy still increase as we increase the radius, but plateaus at a smaller
radius (between 50 and 70 meters) compared to a more aggressive
responsiveness. Accordingly, for the purpose of our study we select radii of
10, 25, and 100 meters.