Transcript Computational Geometry and Spatial Data Mining

Computational Geometry
and Spatial Data Mining
Marc van Kreveld
Department of Information and
Computing Sciences
Utrecht University
Two-part presentation
• Morning:
Introduction to computational geometry
with examples from spatial data mining
• Afternoon:
Geometric algorithms for spatial data
mining (and spatio-temporal data mining)
Spatial data mining and computation
• “Geographic data mining involves the
application of computational tools to reveal
interesting patterns in objects and events
distributed in geographic space and across time”
(Miller & Han, 2001) [  data analysis ? ]
• Large data sets 
attempt to carefully define interesting patterns
(to avoid finding non-interesting patterns) 
advanced algorithms needed for efficiency
Introduction to CG
• Some words on algorithms and efficiency
• Computational geometry algorithms
through examples from spatial data mining
– Voronoi diagrams and clustering
– Arrangements and largest clusters
– Approximation for the largest cluster
Algorithms and efficiency
• You may know it all already:
• Please look bored if you know all of this
• Please look bewildered if you haven’t got a
clue what I’m talking about
Algorithms
• Computational problems have an input
size, denoted by n
– A set of n numbers
– A set of n points in the plane (2n coordinates)
– A simple polygon with n vertices
– A planar subdivision with n vertices
• A computational problem defines
desired output in terms of the input
Algorithms
• Examples of computational problems:
– Given a set of n numbers, put them in sorted
order
– Given a set of n points, find the two that are
closest
– Given a simple polygon P with n vertices and
a point q, determine if q is inside P
P
q
Algorithms
• An algorithm is a scheme (sequence of
steps) that always gives the desired output
from the given input
• An algorithm solves a computational
problem
• An algorithm is the basis of an
implementation
Algorithms
• An algorithm can be analyzed for its
running time efficiency
• Efficiency is expressed using O(..) notation,
it gives the scaling behavior of the
algorithm
– O(n) time: the running time doubles (roughly)
if the input size doubles
– O(n2) time: the running time quadruples
(roughly) if the input size doubles
Algorithms
• Why big-Oh notation?
– Because it is machine-independent
– Because it is programming languageindependent
– Because it is compiler-independent
unlike running time in seconds
It is only algorithm/method-dependent
Algorithms
• Algorithms research is concerned with
determining the most efficient algorithm
for each computational problem
– Until ~1978: O(n2) time
– Until 1990: O(n log n) time
– Now: O(n) time
}
polygon
triangulation
Algorithms
• For some problems, efficient algorithms
are unknown to exist
• Approximation algorithms may be an
option. E.g. TSP
– Exact: exponential time
– 2-approx: O(n log n) time
– 1.5-approx: O(n3) time
– (1+)-approx: O(n1/) time
Voronoi diagrams and clustering
• A Voronoi diagram stores proximity among
points in a set
Voronoi diagrams and clustering
• Single-link clustering attempts to maximize
the distance between any two points in
different sets
Voronoi diagrams and clustering
Voronoi diagrams and clustering
Voronoi diagrams and clustering
• Algorithm (point set P; desired: k clusters):
– Compute Voronoi diagram of P
– Take all O(n) neighbors and sort by distance
– While #clusters > k do
• Take nearest neighbor pair p and q
• If they are in different clusters, then merge them
and decrement #clusters (else, do nothing)
Voronoi diagrams and clustering
• Analysis; n points in P:
– Compute Voronoi diagram: O(n log n) time
– Sort by distance: O(n log n) time
– While loop that merges clusters: O(n log n)
time (using union-find structure)
• Total: O(n log n) + O(n log n) + O(n log n)
= O(n log n) time
Voronoi diagrams and clustering
• What would an “easy” algorithm have given?
– really easy: O(n3) time
– slightly less easy:
O(n2 log n) time
n3
time
10 n2 log n
1000 n log n
100
200
300
Computing Voronoi diagrams
• By plane sweep
• By randomized incremental construction
• By divide-and-conquer
 all give O(n log n) time
Computing Voronoi diagrams
• Study the geometry, find properties
– 3-point empty circle  Voronoi vertex
– 2-point empty circle  Voronoi edge
Computing Voronoi diagrams
• Some geometric properties are needed,
regardless of the computational approach
• Other geometric properties are only
needed for some approach
Computing Voronoi diagrams
• Fortune’s sweep line algorithm (1987)
– An imaginary line moves from left to right
– The Voronoi diagram is computed while the
known space expands (left of the line)
Computing Voronoi diagrams
• Beach line: boundary between known and
unknown  sequence of parabolic arcs
– Geometric property: beach line is y-monotone
 it can be stored in a balanced binary tree
Computing Voronoi diagrams
• Events: changes to the beach line =
discovery of Voronoi diagram features
– Point events
Computing Voronoi diagrams
• Events: changes to the beach line =
discovery of Voronoi diagram features
– Point events
Computing Voronoi diagrams
• Events: changes to the beach line =
discovery of Voronoi diagram features
– Circle events
Computing Voronoi diagrams
• Events: changes to the beach line =
discovery of Voronoi diagram features
– Circle events
Computing Voronoi diagrams
• Events: changes to the beach line =
discovery of Voronoi diagram features
– Only point events and circle events exist
Computing Voronoi diagrams
• For n points, there are
– n point events
– at most 2n circle events
Computing Voronoi diagrams
• Handling an event takes O(log n) time due
to the balanced binary tree that stores the
beach line  in total O(n log n) time
Intermediate summary
• Voronoi diagrams are useful for clustering
(among many other things)
• Voronoi diagrams can be computed
efficiently in the plane, in O(n log n) time
• The approach is plane sweep (by Fortune)
Figures from the on-line animation of
Allan Odgaard & Benny Kjær Nielsen
Arrangements and largest clusters
• Suppose we want to identify the largest
subset of points that is in some small region
– formalize “region” to circle
– formalize “small’’ to radius r
Place circle to
maximize point
containment
r
Arrangements and largest clusters
• Bad idea: Try m = 1, 2, ... and test every
subset of size m
• Not so bad idea: for every 3 points, compute
the smallest enclosing circle, test the radius
and test the other points for being inside
Arrangements and largest clusters
• Bad idea analysis: A set of n points has
roughly ( mn ) = O(nm) subsets of size m
• Not so bad idea analysis: n points give ( n3 )
= O(n3) triples of points. Each can be
tested in O(n) time  O(n4) time algorithm
Arrangements and largest clusters
• The placement space of circles of radius r
C
p
A circle C of radius r contains
a point p
if and only if
the center of C lies inside a
circle of radius r centered at p
Arrangements and largest clusters
• The placement space of circles of radius r
Circles with center here
contain 2 points of P
Circles with center here
contain 3 points of P
Arrangements and largest clusters
• Maximum point containment is obtained
for circles whose center lies in the most
covered cell of the placement space
Computing the most covered cell
• Compute the circle arrangement in a
topological data structure
• Fill the cells by the cover value by
traversal of the arrangement
1
0
1
2
1
2 3
1
The value to be
assigned to a cell
is +/- 1 of its
(known) neighbor
Computing the most covered cell
• Compute the circle arrangement:
– by plane sweep: O(n log n + k log n) time
– by randomized incremental construction in
O(n log n + k) time
where k is the complexity of the arrangement;
k = O(n2)
If the maximum coverage is denoted m, then k =
O(nm) and the running time is O(n log n + nm)
Computing the most covered cell
• Randomized incremental construction:
– Put circles in random order
– “Glue” them into the topological structure for
the arrangement with vertical extensions
Every cell has ≤ 4
sides (2 vertical and
2 circular)
Computing the most covered cell
Every cell has ≤ 4
sides (2 vertical and
2 circular)
Trace a new circle from its leftmost
point to glue it into the arrangement
 the exit from any cell can be
determined in O(1) time
Computing the most covered cell
• Randomized analysis can show that adding
one circle C takes O(log n + k’ ) time, where
k’ is the number of intersections with C
• The whole algorithm takes O(n log n + k)
time, where k =  k’ is the arrangement size
• The O(n + k) vertical extensions can be
removed in O(n + k) time
Computing the most covered cell
• Traverse the arrangement (e.g., depth-first
search) to fill the cover numbers in O(n + k)
time
• into a circle
+1
• out of a circle
-1
Intermediate summary
• The largest cluster for a circle of radius r
can be computed in O(n log n + nm) time
if it has m entities
• We use arrangement construction and
traversal
• The technique for arrangement
construction is randomized incremental
construction (Mulmuley, 1990)
Largest cluster for approximate
radius
• Suppose the specified radius r for a cluster
is not so strict, e.g. it may be 10% larger
Place circle to
maximize point
containment
r
(1+) r
If the largest cluster of radius r has m entities, we must
guarantee to find a cluster of m entities and radius (1+) r
Approximate radius clustering
• The idea: snap the entity locations to grid
points of a well-chosen grid
Snapping should not
move points too much:
less than r /4
 grid spacing r /4
works
Approximate radius clustering
• The idea: snap the entity locations to grid
points of a well-chosen grid
1
1
1 1
2
2
1 1
1
2 2
1
1 1
1
1 1
1
1
1 1
1
1 2
1
1
1
1
1
For each grid point,
collect and add the
count of all grid points
within distance (1+/2) r
Approximate radius clustering
• The idea: snap the entity locations to grid
points of a well-chosen grid
1
1
1 1
2
2
1 1
1
2 2
1
1 1
1
1 1
1
1
1 1
1
1 2
1
1
1
1
For each grid point,
collect and add the
count of all grid points
within distance (1+/2) r
1
Collected count = 10
Approximate radius clustering
• The idea: snap the entity locations to grid
points of a well-chosen grid
1
1
1
2
1
2
1
1
1
1
1
1
8
92
110
6
1
1
2
1
1
1
1
1
1
1
2
1
1
1
1
For each grid point,
collect and add the
count of all grid points
within distance (1+/2) r
Approximate radius clustering
• Claim: a largest approximate radius
cluster is given by the highest count
1
1
1
2
1
2
1
1
1
1
1
1
8
92
110
6
1
1
2
1
1
1
1
1
1
1
2
1
1
1
1
Approximate radius clustering
• Let Copt be a radius-r circle with the most
entities inside
• Due to the grid spacing, we have a grid point
within distance r /4 from the center of Copt
that must have a count
Approximate radius clustering
• Snapping moves entities at most r /4
• C and Copt differ in radius r /2
 no point in Copt can have moved outside C
• Snapped points inside C have their origins
inside a circle of radius at most (1+) r
 no points too far from C
can have entered C
Approximate radius clustering
• Intuition: We use the  in different places
– Snapping points
– Trying only circle centers on grid points
... and we guarantee to test a circle
that contains all entities in
the optimal circle, but not
other entities too far away
Approximate radius clustering
• Efficiency analysis
– n entities: each gives a count to O(1/2) grid
cells
– in O(n /2) time we have all collected counts
and hence the largest count
Exact or approximate?
• O(n log n + nm) versus O(n /2) time
• In practice: What is larger: m or 1 /2 ?
– If the largest cluster is expected to be fairly
small, then the exact algorithm is fine
– If the largest cluster may be large and we
don’t care about the precise radius, the
approximate radius algorithm is better
Concluding this session
• Basic computational geometry ...
Voronoi diagrams, arrangements,
-approximation techniques
... is already useful for spatial data mining
• Afternoon: spatial and spatio-temporal data
mining and more geometric algorithms