# Voronoi Diagrams

- Problem: We have a map with n points in there (p_1, p_2, ..., p_n) and we want
  to identify for each point q what is the point p_i.

* For the PPT: We have **n** Tambos in a map and we want to identify regions in
  this map such that for each point in a region, the closest Tambo is the one
  in that region

* Voronoi assignment model: Assign every point to the nearest city
* Voronoi diagram: Subdivision induced by the Voronoi assignment model

1: Dado n Tambos en un mapa, identificar regiones tal que cada region tenga un solo Tambo y para cada punto dentro de esa región el Tambo más cercano sea el que está en esa regionProblema motivacional
2: Dado n Tambos en un mapa, determinar en que punto conviene conviene abrir un nuevo Tambo de manera que la distancia con el Tambo más cercano sea la máxima posible

Formaly:
Let
* P = {p_1, p_2, ..., p_n} where p_i is a point in R^2
* V(p_i) = {q in R^2 | dis(q, p_i) lt dis(q, p_j) j in [1, n], j != i}

Then,  Voronoi diagram of P = Vor(P) = Union V(p_i) i in [1, n]

* Mediatrix of points p, q is the line perpendicular to pq and intersects with
  its middle point

* def. h(p, q) is the half-plane of the mediatrix of p and q where p is located

Then, we have h(p, q) = {r in R ^ 2 | dis(r, p) < dis(r, q)}

Then V(p_i) = Intersection (h(p_i, p_j)) j in [1, n], j != i

**Theorem 1** If all points of P are collinear -> Vor(P) consists of
n - 1 parallel lines, Otherwise, Vor(P) is connected and its edges are either segments or half-lines.

**Proof**

If all points of P are collinear then all its mediatrices are collinear, then
its intersections are parallel, so Vor(P) consists of n - 1 parallel lines.
Else
- Suppose that an edge e that is a full line in Vor(P), then it is the mediatrix
  of two points (p_i, p_j), but there exists a point p_k not collinear with
  p_i and p_j, so the mediatrix of p_k, p_j intersects with e, then as h(p_j,
  p_i) intersection h(p_j, p_k) != empty set -> e if not in Vor(P).
- For every i, V(p_i) is the intersection of a finite number of convex sets, then V(p_i) is
  convex.

So far, we have the V(p_i) has at most n - 1 vertices and edges, so Vor(P) have
O(n ^ 2) vertices and edges. But, is there a tigh bound ?

**Theorem 2** For n >= 3, Vor(P) has at most 2n - 5 and the number of edges is at most 3n - 6.

**Proof**
If the points are collinear, then we have n - 1 vertices and edges, then it
holds.
Else, we add a vertex at infinity and connect it with with the half-infinity
edges of Vor(P), then we have a plannar graph. Then, by Euler's formula

(V + 1) - E + n = 2
2E = sum of degrees >= 3 * (V + 1)

-> 2E >= 3 * (2 + E - n)
2E >= 6 + 3E -3n
**3n - 6 >= E**

3n - 6 >= V + 1 + n - 2
**2n - 5 >= V**

Def. C_P(q) = {B(q, r), r = max(r' | B(q, r') intersection P = Empty set}

**Theorem 3:
(i) A point q is in V iff |clausura(C_P(q)) intersection P| >= 3
(ii) m(p_i, p_j) define an edge of E iff exists q in the m(p_i, p_j) |
  |clausura(C_P(q)) insertection P| = {p_i, p_j}

**Proof**
(i)
(->)
Let p_i, p_j, p_k be in |clausura(C_P(q) intersection P| -> dis(q, pi)
= dis(q, p_j) = dis(q, p_k) and as the interior of C_P(q) is empty, then q is
in the boundary of V(p_i), V(p_j), V(p_k), then q is in V
(<-)
Every vertex q in V has at least degree 3. Then exists p_i, p_j, p_k |
it is in the boundary of V(p_i), V(p_j), V(p_k) and dis(q, p_i) = dis(q, p_j)
= dis(q, p_k) and there is not a closer point to q. Then |Clausura(C_P(q)
intersection P| >= 3

(ii)
(->)
dis(q, p_i) = dis(q, p_j) <= dis(q, p_k) k in [1, n] and by (i) it is not
a vextex -> it is part on an edge.
(<-)
For q in the interior of the edge defined by m(p_i, p_j) in Vor(P), |clausura(C_P(q)) intersects P| included in {p_i, p_j} if
there were a p_k in |clausura(C_P(q) intersects P| -> q would be a vextex by
(i) (-> <-). Then clausura(C_P(q) intersects P) = {p1, p2}

# Brute Force

For each p_i compute the intersection of the half-planes h(p_i, p_j) [i != j]
using the alogirhtm presented in Chapther 4. Then, each cell can be computed in
O(n log n), so the total complexity is O(n ^ 2 log n)

But, we can design a faster algorithm with a plane sweep algorithm.

The idea of a plane sweep algorithm is to sweep a line over the plane while
maintaining information of the region already visited and updating it at
special points - the event points.

For this problem we will use a sweep line from top to bottom maintaining
information about the part of the Voronoi diagram of the points above the line
that cannot be change by points below the line.

Let l be the sweep line.

* For a point q above l, the distance from q to l is leq than to any point
  above l. Hence if dis(q, p_i) <= dis(q, l) for some point p_i in l+, them the
  region of q won't change. The set of points that are closer to q than to l
  form a parabola.
* For every point in l+ we can get its parabola and intersect all of them to
  get a sequence of parabolic arcs that we will call beach line. That is, the
  beach line for l+ if a function that for each x-coordinate associated the
  lowest point of the parabolas of each p_i in l+

**Observation** The intersection of two parabolic arcs (breackpoints) lie on
edges of the Voronoi diagram. It follows from Theorem 2 (ii).

Then, as we move our sweep line l, we maintain its beach line.

We will call the event when l reach a new point a site event.

How the beach line changes in a site event.

**Affirmation 1** The only way in which a new arc can appear on the beach line
is through a site event

**Proof**
By contradiction
- Case 1. It appear tangent to another parabola (no sense)
- Case 2. It appear in a breakpoint (its parabola wont appear)

**Therefore, each site event can**
* Rise one new arc
* Split one existing arc into two

So, the beach line consist of at most 2n - 1 parabolic arcs.

- Lets call a circle event when the line reaches the lowest point of a circle defined by three points
  that define consecutive arcs of the beach line

**Affirmation 2** The only way in wich an existing arc can dissapear from the
beach line is through a circle event

**Proof**
Left to the reader as an exercise

# Data structures
- Doubly-connected edge list for the Voronoi diagram under construction. But Voronoi diagram has edges
  that are half-line of full lines, them we will add a big bounding box. Then, we will compute the Voronoi
  diagram inside this box.

- Balanced binary search tree T for the beach line.
* Leaves correspond to arcs of the beach line
* Internal points represent breakpoints in the form (p_i, p_j)
* Leaves also store a pointer to a node in the event queue (the circle event in
wich it will dessapear)
* Internal nodes have a pointer to the hald-edge in the doubly-connected edge
  list

- The event queue Q is implemented as a priority queue where the order is based
  of y-coordinate.
* For the site event we simply store the point itself
* Fot a circle event we store the lowest point of the circle, with a pointer to
  the leaf of T that represents the arc that will desappear

How to detect the events ?
- Site event: We know all of them
- Circle event:
* Idea 1:
* Idea 2:

**Affirmation 3:** Every Voronoi vertex is detected by means of a circle event.

**Proof**


# Pseudocode