Transcript Kinetic algorithms: approximation and trade-offs

Kinetic Algorithms:
Approximation and Trade-offs
Pankaj K. Agarwal
Duke University
Motivation
Applications
•
•
•
•
Location based services
Animation
Physical simulation
Mobile and wireless networks
Need algorithms and data structures for
processing, analyzing, querying moving objects
Dynamic data structures not suitable for handling
moving objects
Modeling Motion
p(t) = (x(t),y(t)): Position of p at time t
x(t), y(t): polynomials
Degree of motion: max degree of x(), y()
Linear motion: Degree = 1
• p(t) = a t + b, a, b in R2
Mostly assume motion to be linear
Trajectory of points can change
Trajectory can be piecewise linear
Early Work
Off-line setting: Entire motion known in advance
Bound the # combinatorial/topological changes in
geometric attributes under algebraic motion
[Atallah 1985]
• Convex hull, closest pair, Voronoi diagram
# combinatorial changes in
•Convex hull: ≈n2
•closest pair: Q(n2)
Early Work: Open Problems
# edge-flips in Delaunay triangulation of a point
set, each point moving with fixed velocity
• Upper Bound O(n3)
• Lower Bound W(n2)
# changes in the smallest disk containing points
• Smallest disk is defined by 2 or 3 points lying on its
boundary
Kinetic Data Structures
[Basch, Guibas, Hershberger 1999]
Event based framework
Store some auxiliary information to expedite the
simulation
D
A
external
event
D
B
A
internal
event
A
B
A
A
B
B
ABC
C
A
•A<B, C<D, B<D hold: no
computation necessary
(certificates)
D
•A=B, C=D, or B=D: update
structure (events)
A
AD
C C D
AD
Kinetic Data Structure (KDS)
Maintain a set of certficates
Certificates provide a proof of the correctness of
first event
the structure
in global
Proof of
Certificate
queue
Correctnes
Failure
Determine when a certificate fails: event
s
• Event times are roots of certain polynomials
Update theProof
structure at an
event and compute new
Structure
Update
certficatesUpdate
Store events in a global priority queue
Kinetic Data Structures (KDS)
Performance of KDS measured as
# events (efficiency)
# certificates (compactness)
Time spent at each event (locality)
Efficient KDS developed for many problems
[A. et al. 2001][Guibas 2004]
Issues
 Too many events for many KDS
 Computing event times is expensive
 Querying moving objects
• No need to maintain the structure at all times
Trade Offs in KDS
Efficiency vs Approximation
Efficiency vs Accuracy
Querying Moving Objects
• Range searching, nearest-neighbor searching on
moving points
• No need to maintain the structure at all times
I. Efficiency vs Approximation
KDS using Coresets
S: Set of n moving points in R2
Maintain the diameter (width, smallest enclosing
box) of S
 [A., Guibas, Hershberger, Veach]
• Diametral pair can change Q(n2) times
• KDS with ~ n2 events
Can we maintain the approximate diameter of S
more efficiently?
• Is there a small subset Q of S s.t. for all t
diam(Q(t)) ≥ (1-e) diam(S(t))
Q: coreset of S
Extent of Functions
F={f1, …, fn}: d-variate functions
• UF: Upper envelope of F UF(x) = maxi fi(x)
• LF: Lower envelope of F LF(x) = mini fi(x)
Extent: EF(x) = UF(x) - LF(x)
e-kernel: G is e-kernel of F
if (1-e) EF(x) ≤ EG(x)
Coresets for Moving Points
S: Set of n moving points in R2
w(u,S(t)): Directional width of S(t)
in direction u
A subset Q is e-kernel of S if
For u in S1, t in R
(1-e)w(u,S(t)) ≤w(u,Q(t))
fi(u,t): ‹pi(t), u›, F={f1…fn}
Claim: w(u,S(t)) = EF(t)
e-kernel of F
e-kernel of S
Kernels of Moving Points
Theorem [A., Har-Peled, Varadarajan]
F={f1, …, fn}: d-variate polynomials of fixed degree;
e > 0 parameter
An e-kernel of F of size 1/eO(1) can be computed in
time O(n+ 1/eO(1)).
Corollary: S: n points moving with fixed velocity in
2D, e > 0 parameter.
An e-kernel of S of size O(1/e3/2) can be computed
in time O(n+ 1/e3).
Maintaining a Bounding Box
Maintain an e-approximation of the bounding box of S
 Compute an e-kernel Q of S
 Smallest Bounding box defined by:
left-,right, top, and bottom-most points
 Use KDS to maintain these 4 points of Q
 Events: When one of them changes
Same approach works for maintaining
width, diameter, … approximately
Bounding Box: Quality of Kernels
10,000 moving points
Trajectories linear of quadratic
Error < 0.02 for kernel of size 32
Linear Motion
Quadratic Motion
Bounding Box: # Events
Exact Algorithm
Approximation Algorithm
Kinetic Convex Hull with Coresets
Convex hull of 10,000
moving points
Quality of Approximation
Quality
over 200
Quality
Quality
of Width
of Diameter
Random Directions
Kinetic Event Distribution
Original Set
* Input: 10,000 linearly moving points
Coreset
Kinetic Triangulations
Delaunay triangulation in R2
• O(n3) edge flips
An arbitrary triangulation in R2
• ≈n2 edge flips [A., Wang, Yu 2004]
Can we maintain an almost Delaunay triangulation
with ≈n2 edge flips?
[A., Guibas, Gao, Koltun, Sharir 2006]
Maintain a subgraph of Delaunay
triangulation that
• contains W(n) Delauanay edges
•contains all wide Delaunay edges
• performs ≈ n2 edge flips
Is there a good definition of almost Delaunay triangulation?
Efficiency vs Accuracy
Robust KDS
Event Scheduling in KDS
 The kinetic data structure framework
Proof of
Correctness
Certificate
Failure
Proof
Update
Structure
Update
 Events: Computing roots of a polynomial
 KDS assumes events are processed in correct order
* Need exact root comparison; EXPENSIVE!
* Need degeneracy handling (simultaneous events); PAINFUL!
first event in
global queue
Out-of-Order Event Processing
 What if using floating point arithmetic to compute and
compare event times inexactly?
* Pros: cheaper arithmetic operations
* Cons: events may now be processed in the wrong order
scheduled
A(t )
B (t )
processed
ACB
CBA
CAB
In-order: ABC
BCA
ABC
Out-of-order: BAC
C (t )
Not scheduled because its computed
t
event time is before current time
Out-of-Order Event Processing
Issues in out-of-order event processing
* Does the KDS fall into an infinite loop?
* Can an event be delayed for too long?
* Can error in the maintained structure be too large?
[Abam, A., de Berg, Yu, 2006]
Robust KDS to address these issues
• KDS is correct at all times except near the event times
• No event is delayed too long
• Bonus: Degeneracies are handled automatically
Model of Robust KDS
 Root computation procedure CROP
* f (t ) : input polynomial; e : error bound in CROP
* CROP( f (t ) ) does the following
(1) find set of disjoint, open event intervals I1 , , I k
s.t. each I i  e and they cover all roots
(2) find parity of the number of roots lying in each I i
(3) return intervals with odd number of roots
I1
I2
I3
Computing Event Times
I2
I1
_
_
+
 last
I3
tcurr
+
last1
If Certificate conforms to sign( tcurr )
schedule a future event at last1 ;
Otherwise schedule a past event at  last .
Computing Event Times
c: failing certificate;  c : polynomial associated with c
A past event…
A future event…
 last tcurr last1
 last tcurrlast1
Robust Kinetic Sorting
I may encounter
a past event…
The new
EventTime(.)
* Almost the same as traditional kinetic sorting algorithm…
(but not always, e.g., robust kinetic convex hull)
Nice Properties
 The KDS does not fall into an infinite loop
 List is correct except within e-neighborhood of actual event
times
t
Nice Properties
 Events may be delayed by at most O(ne ) time long
tcurr
 Even when list is incorrect, it is still close to true
sorted list geometrically
xi (tcurr )  xˆi (tcurr )  neVmax
xi : i-th pt in maintained list
x̂i : i-th pt in sorted list
Vmax: maximum velocity over
time interval tcurr  e ,tcurr 
Experimental Results: Kinetic Sorting
Input
Experimental Results
Input
Experimental Results
Input
Other Robust KDS
[Abam, A., de Berg, Yu, 2006]
Kinetic tournament
Convex hull, kd-tree, range-tree, …
Is there a robust KDS for Delaunay triangulation?
• Find a sequence of edge-flips to convert a selfintersecting triangulation to Delaunay triangulation
Soft KDS
[Czumaj, Sohler 2005]
Approximate KDS
Repair the structure only when necessary
Use the ideas from property testing to ensure
KDS is almost correct with high probability
Competitive analysis to measure the performance
of KDS
III. Querying Moving Objects
Kinetic Range Searching
S: Set of points, each moving with fixed velocity in R2
Preprocess S into a data structure:
 (Q1) Given rectangle R at time t, report all points S(t)∩R
 (Q2) Given R and time interval [a,b], report all points of
that pass thru R during the time interval [a,b]
KDS Approach
Kientic range trees [A., Arge, Erickson 2003]
• O(n log n) space, O(log n + k) query (Q1)
• Use KDS approach to update range tree
 Q(n2) events; O(log2 n) (amortized) time at each event
• Queries have to arrive in chronological order
Kinetic kd-trees [A. Gao, Guibas 2003]
• O(n) space, O(n1/2 + k) query (Q1)
 Q(n2) events; O(log2 n) (amortized) time at each event
• Queries have to arrive in chronological order
What if queries do not arrive in chronological
order? Why spend time processing events?
Kinetic Range Searching
Partition tree based approach [A., Arge, Erickson]
O(n) space, O(n1/2 + k) query time
O(log2 n) insertion/deletion of a point
Answering (Q1) query
A similar approach works for (Q2) queries
Time-Responsive Indexing
 Time-responsiveness
* Near future queries need to be answered more quickly
x
* Optimize structure for near future
* Approximate distant future
 Results [A., Arge, Erickson, Yu, 2004]
l3
l2
* Orthogonal range queries in R1 , R2
~n space, (f(tq)/n)1/2 + logO(1) n + k query time
f(tq): # events between current time and tq
 (t q )  O(n)
 (tq )  W(n2 )
polylog n  k
n1/ 2  k
l4
l1
t
(near future)
(distant future)
Example: 1D Time-Responsive
Indexing
 S (t ): set of linearly moving points in R1
* Given interval [ x1 , x2 ]and time t q , report S (t q )  [ x1 , x2 ]
 In tx-plane, reduces to stabbing query
* Report all lines intersecting a vertical
segment {t q }  [ x1 , x2 ]
 Overall structure
x
x2
x1
* Divide tx-plane into log n slabs
* i-th slab contains 2 i  n events (vertices)
* A window structure for each slab to answer stabbing query
tq
t
Window Structure
 Hierarchical triangulation of the i-th slab
* ~ n / 2 itriangles
* Each triangle intersects at most 2i lines
x
(2i / n)-cutting
 Partition tree for each triangle
* Size: 2i , query time: 2i / 2
 Overall
* Space: ~ n, query: 2  polylog n  k
(note that  (tq )  2i)
* Update every other O (n) events
e
(O(n ) amortized per event)
i/2
t
cutting tree
partition tree
References
[Abam, Agarwal, de Berg, Yu, 2006] Out-of-order event processing in kinetic data
structures. ESA’06.
[Abam, de Berg, 2005] Kinetic sorting and kinetic convex hulls. SoCG’05.
[Agarwal, Arge, Erickson, 2003] Indexing moving points. J. Comput. Syst. Sci., 66(1).
[Agarwal, Arge, Erickson, Yu, 2004] Efficient tradeoff schemes in data structures for
querying moving objects. ESA’04.
[Agarwal, Arge, Vahrenhold, 2001] Time responsive external data structures for
moving points. WADS’01.
[Agarwal, Gao, Guibas, Koltun, Sharir, 2006] Stable Delaunay triabgulation,
manuscript.
[Agarwal, Har-Peled, Varadarajan, 2004] Approximating extent measures of points. J.
ACM, 51(4).
[Agarwal, Wang, Yu] Kinetic triangulation, SOCG’04.
[Czumaz, Sohler, 2005] Soft kinetic data structures, SODA.
[Guibas 2004] Kinetic data structures, Handbook of DCG, 2nd edition,
[Yu, Agarwal, Poreddy, Varadarajan, 2004] Practical methods for shape fitting and
kinetic data structures using coresets. SoCG’04.
Example: Kinetic Sorting
scheduled
processed
A(t )
List: CBA
BAC
BCA
ABC
B (t )
C (t )
Scheduled as a past event because current
configuration is inconsistent with sign B(tcurr )  C (tcurr ) 
tcurr tcurrtcurr
tcurr