Triangulation

Triangulation
An Introduction

Computer Science Department

bernstdh@jmu.edu

Getting Started

Surveying:
- Triangulation is the process of determining the location of a point using angles formed between it and points with known locations
- Trialateration is the process of determining the location of a point using the distances between it and points with known locations
For Our Purposes:
- We won't distinguish between the two

Using Distances in One Dimension

The Problem:
- Given one or more points with known locations, determine the location of a point using the distances between it and those points
Notation:
- $p \in \mathbb{R}$ denotes a point
- $\cal{C(p, \ell)}$ denotes the set of points that are exactly distance $\ell$ from $p$

Using Distances in One Dimension (cont.)

With One Known Location:
- Given the location of the point $p$ and the distance from $p$ to $a$ , determine the location of the point $a$
A Specific Example:
- $p$ is located at 4
- The distance from $p$ to $a$ is 2
Visualization:

Using Distances in One Dimension (cont.)

With One Known Location (cont.):
- You can see from the example that the problem is under-identified when there is only one known location
A Specific Example with Two Known Locations:
- $p$ is located at 4
- The distance from $p$ to $a$ is 2
- $q$ is located at 9
- The distance from $q$ to $a$ is 3
Visualization:

Using Distances in Two Dimensions

Generalizing the Notation:
- $p \in \mathbb{R}^2$ now denotes a point on the plane (i.e., in two dimensions)
Recall:
- A circle is the set of points in a plane that are a given distance (called the radius) from a given point (called the center)
The Implication:
- We need to find the intersections of circles

Using Distances in Two Dimensions (cont.)

An Example:
- $p = (2.0, 3.0)$ and $\ell(p) = 5.0$
- $q = (4.5, 10.0)$ and $\ell(q) = 3.0$
- $r = (7.5, 6.5)$ and $\ell(r) = 2.5$
Visualization:

Using Distances in Two Dimensions (cont.)

Recall:
- Letting $(h, k)$ denote the center of the circle, and $r$ denote its radius, the circle is defined as the set of points $(x, y)$ that satisfy:
  $\sqrt{(x - h)^2 + (y - k)^2} = r$
Squaring Both Sides:
- $(x - h)^2 + (y - k)^2 = r^2$

Using Distances in Two Dimensions (cont.)

Intersection of Two Circles:
- They may not intersect
- They may intersect at one point
- They may intersect at two points
Finding the Intersection:
- Requires a little algebra, but isn't difficult (as long as you account for the different possibilities)

There's Always More to Learn