Transcript Representing Nodes

Geometric Data Structures
Dr. M. Gavrilova
Lecture Plan


Voronoi diagrams
Trees and grid variants
Part 1


Voronoi diagram
Delaunay triangulation
Voronoi diagrams

VD: Thiessen polygons, Delaunay
triangulations, tessellations
Tessellation

Tessellation is often obtained using
Delaunay triangulation.
Voronoi diagram




Given a set of N sites (points) in the plane or a
3D space
Distance function d(x,P) between point x and
site P is defined according to some metric
Voronoi region Vor(P) is the set of all points
which are closer to P than to any other site
Voronoi diagram is the union of all Voronoi
regions
Voronoi Diagram
Voronoi diagram
Definition 1 For a finite set S  E , a Voronoi diagram (VD) Sof
p  S a Voronoi region Vor (p ) such that
d
associates to each
Vor (p )  {x  E d | d ( x, p )  d ( x, q ),q  S  {p}} ,
where d , denotes the Euclidean distance function [Okabe et. al. 92].
Voronoi diagram


Consider the bisector B (p, q )  x d (p, x )  d (q, x ) between two sitesp, q  S
Voronoi diagram in E
d
of a
. The bisector divides the space into two halfspaces. Denote the


halfspace that contains the point p as H (p, q )  x d (p, x)  d (q, x) . By definition this
halfspace also contains the bisector B (p, q) .
Definition 2 For a finite set S  E
d
S
, a Voronoi diagram of
regions Vor (p), p  S such that Vor (p) 
 H (p, q)
qS p
is the collection of all Voronoi
[Okabe et. al. 92].
Voronoi diagram properties
Assumption 1. No four points from the set S are cocircular.
Property 1. Voronoi vertex is the intersection of 3 Voronoi edges
and a common point of 3 Voronoi regions
Property 2. Voronoi vertex is equidistant from 3 sites. It lies in the
center of a circle inscribed between 3 cites
Property 3. Empty circle property This inscribed circle is empty, i.e.
it does not contain any other sites
Property 4. Nearest-neighbor property If Q is the nearest neighbor
of P then their Voronoi regions share an edge (to find a nearest
neighbor it is sufficient to check only neighbors in the VD)
Property 5. Voronoi region Vor(P) is unbounded if and only if P
belongs to the boundary of convex hull of S.
VD properties
Property 1. A Voronoi vertex v is the intersection of 3 Voronoi edges and a common point of
3 Voronoi regions.
p2
1) assume deg( v )  3 .
p1
d v, p1   d v, p 2   d v, p3   ...
...  d v, p n , n  3
Contradicts the non-circumcircularity assumption.
v
p3
pn
2) assume deg( v )  3 . Then both edges are parts of the bisector
B  p1 , p 2  . Both edges lie on the same line. Then v is not a
p1
v
vertex.
p2
VD properties
Property 2. Voronoi vertex is equidistant from 3 sites. It lies in the center
of a circle inscribed between 3 cites.
p2
p1
v
p3
d v, p1   d v, p 2   d v, p3 
VD properties
Property 3 (empty circle property). The inscribed circle is empty, i.e. it does not
contain any other sites.
1) assume a site q lies inside the inscribed circle C .
p1 Then d v, q   rC  d v, p1 . This contradicts the fact
that v  Vor p1 .
p2
v
2) assume q lies on the boundary of the inscribed circle.
q
p3
Then d v, q   d v, p1   d v, p 2   d v, p3 . This
contradicts non-circumcircularity assumption.
VD properties
Property 4 (Nearest-neighbor property). If q is the nearest neighbor of p then their
Voronoi regions share an edge (to find a nearest neighbor it is sufficient to check only
neighbors in the VD)
q
x
p
Then
s
Vor p  and Vor q  don't have common
points. Segment pq crosses the boundary of Vor p 
at a point x . Assume x belongs to the Voronoi edge
between Vor p  and Vor s .
Assume
d p, q   d x, p + d x, q ,
d p, s   d x, p + d x, s , d x, q   d x, s 
because x  Vor s , x  Vor q 
d p, q   d p, s  – contradicts the fact that q
is the nearest neighbor of
p.
VD properties
Property 5. Voronoi region
the convex hull
CH S .
Vor p  is unbounded if and only if
p belongs to the boundary of
p  CH S . Select a ray r  Vor p . r will
r intersect the boundary of CH S . Assume r intersects a
segment s1 s 2 . It is easy to show that if x  r , x  
p
x
then either d x, s1   d x, p  or
s2
r
d x, s 2   d x, p .
x
Contradicts the fact that x  Vor p 
l
2) if p  CH S  then it is possible to draw a line l through p such that
p
all sites of S lie on the same side of l . Select a ray r^l originating at
p . It is easy to show that any x  r is closer to p than to any other site.
Then r  Vor p , i.e. Vor p  is unbounded.
s1
1) assume
Delaunay triangulation
Definition 3. A Delaunay triangulation (DT) is the straight-line dual of the
Voronoi diagram obtained by joining all pairs of sites whose Voronoi
regions share a common Voronoi edge [Delaunay 34].
Follows from the definition:


If two Voronoi regions Vor(P) and Vor(Q) share an edge, then sites P
and Q are connected by an edge in the Delaunay triangulation
If a Voronoi vertex belongs to Vor(P), Vor(Q) and Vor(R), then DT
contains a triangle (P,Q,R)
Delaunay triangulation
DT properties
Assumption 2. No three points from the set S lie on the
same straight line.
Theorem. The straight-line dual of the Voronoi diagram
is a triangulation of S [Preparata and Shamos 85].
Property 5. The circumcircle of any Delaunay triangle
does not contain any points of S in its interior
[Lawson 77].
Property 6. If each triangle of a triangulation of the
convex hull of S satisfies the empty circle property,
then this triangulation is the Delaunay triangulation of
[Lawson 77].
VD and DT
Property 7 For the Voronoi diagram of n points on the plane and its dual
Delaunay triangulation the following relationships are true when n  3 :
v DT  n ,
e DT  eVD  3n  6 ,
f DT  vVD  2n  5 ,
vVD and v DT represent the number of vertices in VD and DT,
correspondingly, eVD and e DT represent the number of edges in VD and DT
f
and DT is the number of triangles in DT
where
DT properties
The edge of the quadrilateral satisfies the local min-max criterion
if the following equation holds:
min ( i )  min ( i )
i
i
A triangulation satisfies the global min-max criterion if every
internal edge of a convex quadrilateral in the triangulation
satisfies the local min-max criterion.
Property 8. The Delaunay triangulation satisfies the global minmax criterion [Lawson 77].
Property 9. If a triangulation of the convex hull of satisfies the
global min-max criterion then it is the Delaunay triangulation of
[Lawson 77].
VD and DT


Both DT and VD effectively represent the proximity
information for the set of sites. They can be easily
transformed into each other.
VD contains geometrical information, while DT
contains topological information.
Generalized Voronoi diagram


Given a set S of n sites (spheres) in ddimensional space
Distance function d(x,P) between a point
x and a site P is defined.
Generalized Voronoi diagram
A generalized Voronoi diagram (GVD) for
a set of objects in space is
the set of generalized Voronoi regions
VorP  x d x, P  d x, Q, Q  S \ {P}
where d(x,P) is a distance function
between a point x and a site P in the
d-dimensional space.
Generalized Delaunay
tessellation
generalized Delaunay triangulation
(GDT) is the dual of the generalized
A
Voronoi diagram obtained by joining all
pairs of sites whose Voronoi regions share
a common Voronoi edge.
General metrics
d x, P
x
Generalized distance functions
Power
d p (x, P)  d (x, p)
Additively weighted
2
P
 r p2
x
d e (x, P)  d (x, p)  r p
d(x,P)
P

Euclidean
d
d (x, P)   ( xi  pi ) 2  rp
x
i 1
rp
d x, P 
P

Manhattan
d
d (x, P)   xi  pi  r p
x
i 1
rp
P

supremum
d (x, P )  max xi  pi  r p
i 1..d
d x, P 
Power and Euclidean Voronoi
diagrams
Q
P
P
Q
B(P,Q)
B(P,Q)
Power bisector
Power diagram and
Delaunay triangulation
Euclidean bisector
Euclidean diagram and
Delaunay triangulation
Manhattan and Supremum VD
Manhattan bisectors
Manhattan diagram and
Delaunay triangulation
Supremum bisectors
Supremum diagram and Delaunay
triangulation
Properties of Generalized VD
and DT






The vertex of generalized Voronoi diagram is a center of a
sphere inscribed between d +1 Voronoi sites (spheres).
The inscribed sphere is empty, i.e. it does not contain any other
sites.
One of the facets of the generalized Voronoi region Vor(P)
defines a nearest-neighbor of P.
A Voronoi region Vor(P) is unlimited if and only if site P belongs
to the convex hull of S.
The sphere inscribed between the sites comprising a simplex of
generalized Delaunay tessellation is an empty sphere.
The power Delaunay tessellation of a set of spheres S is a
tetrahedrization.
Algorithmic Strategies





Incremental
Divide-and-conquer
Sweep-line/plane
Dimension reduction
Geometric decomposition
Algorithmic Strategies






Algorithm development techniques on
example of Voronoi Diagrams
Incremental construction
Divide and conquer
Sweep-plane
Geometric transformations
Dynamic data structures
Incremental construction
INCIRCLE condition
power
Polynomial of 4th order in the
plane
Euclidean
Polynomial of 8th order in the
plane
Supremum
System of linear equations and
inequalities in the plane
Incremental construction

Incremental method outline
Insert new site P
 Perform swap operations on quadrilaterals
where the empty-sphere condition is not
satisfied
Method complexity is O(n2) in the plane.

Sweep-plane algorithm

Algorithm description
 Throw pebbles in the water
 Intersection of waves gives the Voronoi diagram
 Add time as 3rd dimension: waves transform to
pyramids.
 Sweep pyramids with the sweep-plane to get the
Voronoi diagram
Sweep-plane algorithm

Properties
 The complexity of the sweep-plane algorithm in
generalized Manhattan metric is O(n log n).
 Sweep-plane method is not applicable to the
power diagram construction.
Sweep-plane algorithm

An example of a sweep-plane
construction of a Voronoi diagram in L1
metric
Sweep-plane algorithm
Cones in L1
Sweep-plane algorithm
Sweeping the cones
Sweep-plane algorithm
sweep direction
Parabolas
Sweep-plane algorithm
Site event
Sweep-plane algorithm
Site event
Sweep-plane algorithm
two half-bisectors are created
one is growing
Sweep-plane algorithm
The half-bisector changes its direction
Sweep-plane algorithm
Site event
2 half-bisectors created
Sweep-plane algorithm
The half-bisector
Changes its direction
Sweep-plane algorithm
Circle event
Triangle added to DT
2 half-bisectors deleted
1 half-bisector created
Sweep-plane algorithm
Half-bisector
changes its
direction
Sweep-plane algorithm
No more
events
Sweep-plane algorithm
Resulting Voronoi diagram and Delaunay triangulation
Sweep-plane algorithm
Waves in
Manhattan metric
Waves in
power metric
Swap method: from VD to
power diagram


Relationship between Voronoi bisector and power
bisector:
The power bisector is moved relative to the Voronoi
bisector by
r2  r2

p
q
2d ( p, q )
Bisector transformation
Swap method: from VD to
power diagram

Algorithm overview



Inflate VD sites
Transform edges of VD
Perform INCIRCLE test on quadrilaterals and
perform swap operations if needed.
The worst-case complexity of algorithm is O(n2).
Swap method

Voronoi to power
p
p
2
2
e
e
p
e
1
*
p
p
3
*
p
e
3
1
p
p
4
4
(a)
(b)
Dynamic data structures –
swap application
Approach
construct and maintain a dynamic Delaunay
triangulation for the set of moving disks (in some
metric).
 Collisions checks are performed only along the
Delaunay edges.

Dynamic VD and DT
Problem
 Given a set of N moving and/or
changing (i.e. growing) sites
 Construct the VD (DT) for the set
 Maintain the VD (DT) dynamically
Dynamic VD and DT
Dynamic Voronoi diagram
Dynamic Delaunay triangulation
Dynamic VD and DT




Dynamic DT is easier to maintain than dynamic VD
in a sense that the coordinates of VD vertices must
be calculated, while coordinates of DT vertices (the
sites) are already known for any moment of time
As sites move, the topological structure of DT (and
VD) changes only at discrete moments of time,
which are called topological events.
Topological event involves swapping of the diagonal
in a quadrilateral in the DT
In the VD corresponding edge shrinks to zero and
another edge starts to grow
Swap condition
P1
P1
P2
P1
P2
P4
P3
INCIRCLE( P1, P2 , P3 , P4 )  0
P2
P4
P3
INCIRCLE( P1, P2 , P3 , P4 )  0
P4
P3
INCIRCLE( P1, P2 , P3 , P4 )  0
INCIRCLE test
To determine the swap time we have to solve INCIRCLE( P1 (t ), P2 (t ), P3 (t ), P4 (t ))  0
1. Power metric
x1 y1 x12 + y12  r12 1
x 2 y 2 x 22 + y 22  r22 1
x 3 y 3 x 32 + y 32  r32 1
 poly 4 (trajectory )
x 4 y 4 x 42 + y 42  r42 1
2. Euclidean metric
x1  x4 r1  r4 p1
2
r1  x4 y1  y4 p1
2
x1  x4 y1  y4 p1
x2  x4 r2  r4 p2
+ r2  x4 y2  y4 p2
 x 2  x 4 y 2  y 4 p2
x3  x4 r3  r4 p3
r3  x4 y3  y4 p3
x 3  x 4 y 3  y 4 p3
pi   xi  x4  +  yi  y4   ri  r4  , i  1,2,3
 poly8 (trajectory )
2
2
2
3. Manhattan metric (L)
INCIRCLE ( P1 (t ), P2 (t ), P3 (t ), P4 (t ))  linear (trajectory )
2
Dynamic DT maintenance


Preprocessing

Construct the static Delaunay triangulation for the original
site distribution

For every quadrilateral in DT calculate the potential
topological event. Insert all such events into the priority
event queue sorted according to the time order
Iteration

Take the next event from the event queue

Perform the swap operation and update the data structure

Delete topological events planned for the four disappearing
quadrilaterals from the event queue.

Compute the new topological events for the four new
quadrilaterals and insert them into the queue.
Algorithm complexity


Time

Constructing initial static DT - O(N log N)

Each swap - O(1)

Insertion into the priority queue - O(log N)

Deletion from the queue can be performed in O(1)

Number of topological events depends on the trajectories
of moving sites. It can vary from from O(1) up to O(n3)

and even to infinity (in the case of periodic trajectories)

When sites do not move, but just grow, we conjecture that
the number of topological events will not be greater than
O(N) in general case.
Space

DT occupies O(N)

Queue requires O(N) because only one event can be
scheduled for each edge in the DT
Geometric Data Structures:
Part 2: Grid files and tree variants
Part 2



Grid file
Tree
Variants
Geometric data structures
Voronoi diagrams
Regular grid (mesh)
Grid file
Quad tree
k-d tree
Interval tree
Trees



BST – search trees, O(n)
AVL, IPR – balanced O(log n)
B-trees – for indexing and searching in
data bases:



Grow from the leaf level
More compact – faster search
B+, B* - used for indexing, store data
in leaves, nodes are more full
Operations on spatial trees




Spatial queries
Point location
Stabbing query (which
intervals/polygons contain the point)
Window query – which objects
(polygons, points) are intersecting the
given window (polygon)
Spatial queries (2D)



Point query – find an object containing
a point (find Voronoi region containing
a point)
Window query – find an object
overlapping a rectangle
Spatial join – join parts of objects
satisfying some relationship
(intersection, adjacency, containment)
Interval trees




Geometric, 1-dimensional tree
Interval is defined by (x1,x2)
Split at the middle (5), again at the middle (3,7),
again at the middle (2,8)
All intervals intersecting a middle point are stored at
the corresponding root.
(4,6) (4,8)
(6,9)
(2,4)
1
2
3
4
5
6
7
8
9
(7.5,8.5)
Interval trees




Finding intervals – by finding x1, x2 against
the nodes
Find interval containing specific value – from
the root
Sort intervals within each node of the tree
according to their coordinates
Cost of the “stabbing query”– finding all
intervals containing the specified value is
O(log n + k), where k is the number of
reported intervals.
SAM (Spatial Access Method)



Constructs the minimal bounding box (mbb)
Check validity (predicate) on mbb
Refinement step verifies if actual objects
satisfy the predicate.
The grid


Fixed grid:
Stored as a 2D array, each entry
contains a link to a list of points
(object) stored in a grid.
a,b
Page overflow

Too many points in one grid cell:
Split the cell!
Rectangle indexing with grids



Rectangles may share different grid
cells
Duplicates are stored
Grid cells are of fixed size
Grid file vs. grid




In a grid file, the index is dynamically
increased in size when overflow happens.
The space is split by a vertical or a horizontal
line, and then further subdivided when
overflow happens!
Index is dynamically growing
Boundaries of cells of different sizes are
stores, thus point and stabbing queries are
easy
The quadtree




Instead of using an array as an index,
use tree!
Quadtree decomposition – cells are
indexed by using quaternary B-tree.
All cells are squares, not polygons.
Search in a tree is faster!
Grid file

Example of a grid file
Linear quadtree


B+ index – actual references to
rectangles are stored in the leaves,
saving more space+ access time
Label nodes according to Z or “pi” order
Linear quadtree
Level of detail increases as the number
of quadtree decompositions increases!
Decompositions have indexes of a form:

00,01,02,03,10,11,12,13, 2,300
301 ,302 ,303 ,31 ,32 ,33
 Stores as Bplus tree
Finer Grid
R-tree
 Each object is decomposed and stored
as a set of rectangles
 Object decomposition: larger areas of a
grid are treated as one element
 Raster decomposition: each smaller
element is stored separately
R-trees
R-tree


Objects are grouped together according to
topological properties not a grid.
More flexibility.
R * tree- Optimizes


Node overlapping
Areas covered by the node
R+ tree – B+ tree, bounding rectangles do not
intersect
K-d tree



Used for point location, k –number of
the attributes to perform the search
Geometric interpretation – to perform
search in 2D space – 2-d tree
Search components (x,y) interchange
K-d tree
d
d
c
e
f
b
a
f
b
c a
e
Conclusions

Numerous applications exist based on
Voronoi diagram methodology and
tree/grid based data structures.