Transcript Slides

Static & Dynamic
Maintenance of Kinematic Structures
Spheres, Molecules, and Hidden Surface Removal
D. Halperin and M-H. Overmars
Dynamic Maintenance of Kinematic Structures
D. Halperin, J-C. Latombe and R. Motwani
Presented by Iftah Gamzu
11
Agenda
 Static case:
 Hard Sphere Model
 Molecules Special Properties
 Data Structures for Answering Intersection Queries
 Computing the Boundary of a Molecule
 Dynamic case:
 Graph Theoretic Definition
 Abstract Data Structure for Answering Intersection Queries
 Online Maintenance Case for Path / Trees
 Offline Maintenance Case
 Background for future lectures (if time allows):
 Hidden Surface Removal (Static Case)
2
Static Case
 Goal: devise techniques to represent and manipulate a
static collection of overlapping spheres in R3 .
 Motivation: molecular biology
 representation of molecular configurations (e.g. union
boundary of a molecule).
 manipulation of molecular configurations (e.g.
collision detection).
3
Hard Sphere Model
 Each atom in the molecule is
represented as a sphere in R3
 Spheres can interpenetrate one
another
 There are recommended values
for:
1) Radios of each sphere (e.g. van der
Waals radii)
2) Distance between centers of each pair of
spheres
Acetyl
4
Molecule Special Properties
Generally, spheres in R3 might be
complex combinatorially arrangement defined by n spheres in
R3 might have complexity of O(n3 )
However, molecules have special properties:
 Atoms centers cannot get too close to one another (repellent
forces)
 Atoms radii range is fairly restricted
5
Main Theorem - Definitions
Atom Radius: ri ( rmin  min ri , rmax  max ri )
i
i
Atom Center: ci
Ball (atom): Bi  { p | d ( p, ci )  ri } 1
Molecule: M  {B1 ,...Bn }
1
d is the Euclidean distance function
6
Main Theorem
if  ,  (positive constants) such that
rmax
(i)

rmin
~
(ii) i B i  { p | d ( p, ci )    ri } does not contain any c j ( j  i )

(i) i Bi intersects a constant number of balls in M
(ii) The maximal combinatorial complexity of the
boundary of the union of balls is O(n)
7
Main Theorem - Proof
(i) i Bi intersects a constant number of balls in M

B  { p | d ( p, ci )  ri  2rmax }
 Every ball in M that
Bi intersects
must lie completely in B
 For each
B j that lies completely
inside B, let
 j  { p | d ( p, c j ) 

2
 rmin }
  j are pair-wise interior-disjoint
8
Main Theorem - Proof
 By volume considerations, the total number of
balls that are completely contained in B cannot
exceed…
 ri  2rmax 
3
 3rmax 
3
 

 216   
3
3





  rmin 
  rmin 
2

2

3
 (i) is proved.
9
Main Theorem - Proof
(ii) The maximal combinatorial complexity of the
boundary of the union of balls is O(n)
Immediately follows from (i) since the number of
features involving Bi on the union boundary is
bounded by the number of balls intersecting it,
which is a constant (O(1)) .
 The complexity of the union boundary of M is
O(n)
10
Main Theorem - Example
max and aver. indicate the maximal and
average number of balls intersecting a single
ball in each molecule.
11
Intersection Queries
 Goal: devise a data structure that can answer intersection
queries with either a point or with a ball whose radius is
bounded by rmax.
 Motivation: molecular biology - computer aided
drug design.


checking whether molecules fit together.
checking whether a particular position in R3 lie inside
or outside the molecule.
12
Intersection Queries – Solution 1
Preprocessing:
Store C (the set of centers of the balls in M) in a three
dimensional range tree suitable for answering:
Given a query axis-parallel box, report the points in C
contained in this box.
13
Intersection Queries – Solution 1
Query:
Given a query ball Q (with radius rQ ), construct a ball Q’ with
rQ and
rmaxconcentric with Q.
radius
 B’ is the axis-parallel bounding box of Q’.
 Query the range search structure on C with the box B’.
14
Intersection Queries – Solution 1
 For each of the answers, check whether the corresponding
ball intersects Q.
Performance:
Preprocessing Space
O(n · log²n)
Preprocessing Time
O(n · log²n)
Query Time
O(log²n)
15
Intersection Queries – Solution 2
Preprocessing:
 Subdivide space into cubes whose side is
2rmax long.
 For each ball in M compute the grid cubes that it intersects (at
most 8 cubes).
 Arrange C (the set of non-empty grid cubes) in a balanced
binary search tree and attach to each cube a list (of constant
number) of balls in M that intersect it.
16
Intersection Queries – Solution 2
Query:
 Given a query ball Q, compute the grid cubes it intersects
(at most 8 cubes).
 For each grid cube, find it in the binary search tree and (if it
exists) check the balls in its list for intersection with Q.
Performance:
Preprocessing Space
O(n)
Preprocessing Time
O(n · logn)
Query Time
O(logn)
17
Intersection Queries – Solution 3
Use hash structure instead of the binary search tree.
Performance:
Preprocessing Space
O(n)
Preprocessing Time
O(n) randomized.
Query Time
O(1)
18
Intersection Queries – Solution 3
Testing Results:
 density of the molecule is more dominant then the size of the
molecule.
19
Computing Boundary
 Goal: devise an algorithm to compute the boundary of a
collection of interpenetrating spheres.
 Motivation: molecular biology

computing van der Waals surface.

computing the approximate solvent accessible surface.

other surfaces…
20
Computing Boundary – cont.
The algorithm also solves the problem of computing
the approximate solvent accessible surface.
Reduction:
Increase the radius of each ball in M by r` (the
radius of the solvent sphere).
New instance with different constants
'
'
( rmin
, rmax
,  ' and  ' ) on which we need to
compute the union boundary.
21
Computing Boundary – Solution
Algorithm Outline:
1) For each ball identify the other balls intersecting it.
Use the intersection query data structure.
2) For each ball compute its contribution to the union
boundary.
 Each pair of intersecting balls (which
none contains the other) defines a circle
that partitions each ball into two parts.
 For each ball, calculate all the circles on
it (a 2D arrangement on the ball) and
decide which faces are on the boundary
(using brute force).
22
Computing Boundary – Solution
3) Transform the local information into global structures
describing the union boundary.
 We start with a face (f) that must be on the boundary (e.g.
the face that has the largest z-coordinate on its boundary).
 Recursively, traverse the neighboring faces (f `) of (f) that
haven’t been visited yet.
23
Computing Boundary – Solution
Performance:
Step 1
Space
Time
O(n)
O(n) randomized
O(n · logn)
deterministic
Step 2
O(n)
O(n)
Step 3
O(n)
O(n)
Preprocessing time + Queries time
24
Computing Boundary – Solution
Testing Results:
SOD
Notice: although steps 1 and 2
theoretically take O(n), step 2
dominates the amount of time
required (larger constant).
25
Dynamic Case
 Goal: devise a data structure that allows us to answer
intersection queries on a moving collection of bodies
connected by joints in R3.
 Motivation:
 conformational search in molecular biology.
 collision detection.
 simulation of hyper-redundant robots.
26
Dynamic Case – cont.
 Concept:
 Assumption: we know how to solve the problem for the static
case – e.g. if the collection represents a molecule then we can
use the previously discussed hash structure.
 Goal: we would like to devise a data structure that will
maintain a collection of static substructures and will be able
to (efficiently) support dynamic operations (e.g. update of
the joint parameter).
27
Dynamic Case – cont.
 Example 1:
 for each link there is a substructure (e.g. hash structure
representing a grid occupancy by a link).
T1
T2
 (joint parameter) update operation  update the coordinate
system transformation (O(1)).
 query operation  each substructure must be queried (O(n)).
28
Dynamic Case – cont.
 Example 2:
 Suppose we knew that the sequence of update and query
operations would have the special feature that all the update
operations modify the same joint. What would be a decent
strategy ?
29
Graph Theoretic Problem Definition
Input: L – articulated linkage of n links with no closed loops.
A tree T(V, E) such that
 Links map to vertices - l1,l2 ,..., ln  V  {v1 , v2 ,...vn }
 Joints map to edges - joint connecting links i and j  (vi , v j )  E
30
Graph Theoretic Problem Definition
Output: D – a dynamic collection of substructures that
supports two operations:
UPDATE (vi , v j , q )
- change joint (edge) parameter to q.
QUERY (...)
- query some region for intersections.
Notes:
 the substructures in D can be viewed as a decomposition of T
(into sub-trees) induced by the removal of a set of edges in E
(marked as BROKEN).
 each substructure represents the space occupied by L-elements
corresponding to a sub-tree of T.
31
Graph Theoretic Problem Definition
Example:
 T is decomposed into 2 sub-trees (i.e. D is made of 2
substructures).
 Each sub-tree’s corresponding L-elements are maintained in a
substructure that represents the space occupied by them.
32
The Abstract Data Structure
Primitive operations:
 BREAK (vi , v j ) - breaks the edge (vi , v j ) (this results in a
partition of the substructure that held (vi , v j ) into two
substructures).
Cost: O(1) if the edge is already BROKEN.
O ( nij ) if the edge is MARGED.
 MERGE (vi , v j ) - merges the edge (vi , v j ) (this results in a
union of the corresponding substructures).
Cost: O(1) if the edge is already MARGED.
O ( nij ) if the edge is BROKEN.
33
The Abstract Data Structure – cont.
O ( nij ) is:
TOTAL cost measure
The total number of vertices that participate in
the operation.
MIN cost measure
The number of vertices in the smaller tree that
participates in the operation.
 The TOTAL cost measure corresponds to a situation where
each operation destroys the old structure(s) and then recomputes new structure(s) from sketch
 The MIN cost measure corresponds to a situation where new
structure(s) can be re-computed by inserting/deleting of
elements.
34
The Abstract Data Structure – cont.
How QUERY is performed ?
For simplicity, assume that T is a serial linkage.
 Let S1 denote the static structure that holds the link v1 , S 2 be
the next static structure along the path and so on.
 Each static structure has a coordinate frame attached to it in
which the links in this structure are described ( S1 has the
universal frame).
35
The Abstract Data Structure – cont.
 For every pair of successive static structures
Si and Si 1we
maintain a rigid transformation Ti which transforms points
described in the frame of Si to the frame of Si 1 .
 Given a query region Q, we query
S1 with Q.
The we query S 2 with Q’ = T1(Q)… and so on.
36
Online Case for Path
Initial state: BROKEN edges are spaced regularly along the path
at intervals of
n .
T
n
n
n
Operations:
 QUERY (...) - as explained.
 UPDATE (vi , v j , q ) -
1. BREAK (vi , v j )
2. Update the q parameter in it (and the transformation).
3. MERGE (vi , v j ) (if not one of the initially BROKEN edges).
37
Online Case for Path – cont.
Time complexity:
QUERY – O( n) – since there are
n substructures
UPDATE – O( n) – for the TOTAL and MIN cost measure.
can we do better ?
38
Online Case for Path – Lower Bound
Adversary Approach:
 If the number of BROKEN edges exceeds
query operation (takes ( n ) ).
n , it request a
 Else (the number of BROKEN edges is fewer then n ) , then
there exists a sub path with more then n vertices and the
adversary inputs operation which involves breaking the middle
most edge in this sub path (takes ( n ) for both TOTAL and
MIN cost measures).
can we gain more strength using randomization?
39
Online Case for Trees – MIN cost
Example (T is a star):
 For the TOTAL cost measure, it is
impossible to find a small number of edges
that will decompose the star into small subtrees  (n) for each operation.
 For the MIN cost measure, do not break
any edge  O(1) for each operation.
40
Online Case for Trees – MIN cost
Definitions:
 Heaviness of an edge
 Heaviness of a tree
 Balance number κ of a tree – the
smallest integer κ such that the
removal of κ-1 edges decomposes it
to κ sub-trees, none of which is κheavy.
Note: κ-heavy  κ’-heavy  κ’ κ
41
Online Case for Trees – MIN cost
Assume that there is a tree T with balance number κ:
Initial state: the BROKEN edges are the set of (at most κ-1)
edges which gives a κ-balanced decomposition.
Operations: the same as for the path case.
Time complexity: O(κ) per operation.
is this bound tight ?
42
Online Case for Trees – MIN cost
How to find a balanced decomposition of T ?
Principles:
 κ is known – if κ is unknown, a binary search for its value can
be performed at the cost of increasing the running time by a
factor of O(log(n)).
 The algorithm:
 Based on DFS, thus takes O(n) time.
 Invariant: on final return to vertex u, the residual sub-
tree rooted at u does not contain any κ-heavy edges.
43
Online Case for Trees – MIN cost
If this
sub-tree
has >
Mustresidual
cut
of theedge
edges
Can’t
be aone
κ-heavy
κ-1 vertices it must be cut.
If each
rone
(r >ofof1)u’s
the
ofchildren
u’s
sub-trees
children
has
rooted
in
have
itsatsubinu’s
children
their
tree more
sub-trees
have
thenatmore
κ most
- 1 vertices
then
κ - 1κ vertices
- then
1 vertices
the
then
decision
the
(at least)
sub-tree
whether
r - rooted
1toofcut
them
itatdepends
umust
doesbe
not
on
contain
cut.
the remainder
any κ-heavy
of the edges.
sub-tree under u.
>κ-1
>κ-1
κ-1
>κ-1
κ-1
κ-1
Can’t be any κ-heavy edges
44
Online Case for Trees – MIN cost
Decompose Algorithm
At final return to vertex u
children v1 ,..., vr with values of n1  n2 ...  nr
If n1    1:
r
nu =1+  ni
i=1
Else let s be the greatest integer such that ns    1
Stage A (s  2):
Delete s  1 of the edges corresponding to children v1 ,..., vs such that
the undeleted edge (ek ) corresponds to vertex vk which is either
Unmarked
(If all are marked) choose the one having minimal mk .
45
Online Case for Trees – MIN cost
Decompose Algorithm
Stage B (s = 1):
r
d =1+ ni
i=2
If v1 in not marked then set p  (u, v1 ), m  0
Else set p  pv1 , m  mv1
If m  d    1 then set nu  d  n1 , mark u, pu  p and mu  m  d .
Else delete (u, v1 ), set nu  d and u unmarked .
46
Online Case for Trees – MIN cost
Decompose Algorithm Example
6
2
d=1
d=1
let
7 s be the greatest integer such that5ns 1  1
3 Stage B (s = 1):
3
1 s be the greatest integer such7 that ns    1
let
4
4 d =1+ 1 n

i
Stage A (s  2): i=2
let s be the
greatest
integer)such
that
ns(u, v1), m  0
3
(
v
in
not
marked
then
set
p
4
1
1
Delete
s

1
of
the
edges
corresponding
7
1
1 to1 children
1
1
1
1
letd=3
sStage
be
the
greatest
integer
such
that
n



1
B (s(m=1):
s
  the
 1)undeleted
then set nedge
 n1 , mark u ,
u  d corresponds
v1 ,..., vs r suchdthat
Stage A (s  2):
mu  m  d .
1 min
1
1 to
1pimal
4
d =1+
u 1 pmand
vertex
 nvki having
k.
r
m=3 / d=1
Delete s i=21 of the edges corresponding to children
n(v11vinsuch
 1: that) the
marked
set pundeleted
 pv , m edge
mv corresponds
v1If,...,
s
r
(m

d


, ved.
to verte
x
v
which
is unm(uark
1 ), set nu  d and u unmarked .
n =1+k n 1) delete
3
1
u
1
1
1

i=1
i
1
Tree with balance number 4
47
Online Case for Trees – MIN cost
Conclusion:
Algorithm DFS-Decompose runs in O(n) on an input
tree T with n nodes, and for any given integer κ, it
returns a κ-balanced decomposition of T if it has
balance number κ, and returns failure otherwise.
48
Online Case for Trees – TOTAL cost
The idea: “breaking a vertex”
Add another primitive that breaks a vertex:
 replace a vertex v by two copies of itself v1 and v2 , with an
edge between them.
 each edge incident to v is assigned to one of its copies.
 There exist a choice of O(
n ) vertices to break such that the
tree is decomposes into O( n ) sub-trees, each of size O( n ).
49
Offline Case for Path – TOTAL cost
The TOTAL problem is NPC

q1 , q2 ,..., qm - ordered sequence of queries.
 v1 , v2 ,..., vn - ordered sequence of vertices in the path.
 update operations translate into grid points u1 , u2 ,..., uk .
UPDATE (v j , v j 1 , q )
operation between
queries qi and qi 1
50
Offline Case for Path – TOTAL cost
Claim: an optimal solution for the problem corresponds to
partitioning R into axis-parallel rectangles R1 , R2 ,..., Rt such that
t
(hi  wi ) is minimized and no rectangle contains a point of U

i 1
in its interior.
vertical
cost of query
edgesiscorrespond
the numbertoof
sub-paths
that
rectangles
have undergone
(substructures)
a change
in the

charge
intersection
the cost
 charge
to the left
the vertical
cost to the
rectangle
portion ofedges.
the lower horizontal edge.
51
Offline Case for Path – TOTAL cost
The specified rectangle partitioning problem is harder than the
TOTAL problem  approximation algorithms to the rectangle
partitioning also approximate the TOTAL problem.
5
 Gonzalez et al – 1.75 approximation in time O ( U )
 Gonzalez et al – 4 approximation in time O( U log U )
It can be proved that TOTAL problem is harder (reduction in
the reverse direction) then the specified rectangle partitioning.
 Equivalency between the two problems.
 The TOTAL problem is NPC.
52
Offline Case for Path – MIN cost
 The MIN problem is NPC ?
 It can be shown that
 O(log( U
OPTTOTAL ( I )  O(OPTMIN ( I )  log( U ))
)) - approximation algorithm
53
Hidden Surface Removal
 Goal: devise an algorithm for hidden surface removal
among a set of intersecting spheres.
 Motivation: molecular biology – molecules display.
54
Hidden Surface Removal – cont.
Algorithms:
 Z-buffer algorithm – most implementations only handle
polyhedral objects. Thus, we need to approximate the spheres
by a triangular meshes  large number of faces  Slow.
 Painter’s Algorithm – define the depth
order on the objects (sorting from back to
front) and then draws the objects in this
order on top of each other  what is the
depth order between intersecting objects ?
55
Hidden Surface Removal – cont.
If the spheres do not intersect ?
The depth order is acquired by sorting the spheres by the zcoordinate of their centers.
And if the spheres intersect ?
Lets look only on pieces of the spheres that
1. constitutes the boundary of the union. And,
2. are part of the visible hemisphere.
and try to define a depth order on them…
56
Hidden Surface Removal – cont.
S1 , S2 ,..., Sn - a collection of spheres sorted by z of their centers.
H i - a hemisphere of Si facing the viewing direction.
H i1 , H i2 ,..., H i ji - a collection of maximal pieces that are part of
the boundary of the union of spheres.
Then
H11 ,..., H1j1 , H 21 ,..., H 2j2 ,...., H n1 ,..., H njn
is a valid depth order for the pieces of the boundary.
i<j
NO
i>j
57
Hidden Surface Removal – cont.
Algorithm:
 Compute the boundary of the of the union.
 Given a viewing direction, cut off the parts that lie outside
the viewable hemisphere.
 Compute the depth order for the spheres and draw the pieces.
Performance:
O(n·log n) + O(n) + O(n·log n) =
O(n·log n) deterministic
58
Questions…
59