Paper Info
Title
A segment-tree based kinetic BSP
Abstract
We present anew technique to maintain a BSP for a set of n moving disj oint segments in the plane. Our kinetic BSP uses O(n log n) storage and it undergoes O(n 2 ) changes in the worst case, assuming that the endpoints of the segments move along bounded-degree algebraically dened trajecto- ries. The response time (the time needed to update the BSP when it undergoes a change) is O(log 2 n). A random- ized variant achieves O(log n) expected response time, while the worst-case response time remains O(log 2 n).The new BSP is based on a simple technique for main- taining a 1-d segment tree on a set of intervals on the real line with moving endpoints. The response time of the ki- netic segment treeisO(log n) intheworst case, and O(1) expected.
Year
DOI
Venue
2001
10.1145/378583.378647
Symposium on Computational Geometry 2013
Keywords
Field
DocType
response time,expected response time,disj oint segment,kinetic bsp,worst-case response time,n log n,intheworst case,log n,new bsp,1-d segment tree,surface reconstruction,kinetics,sample,spread,delaunay triangulation
Discrete mathematics,Binary logarithm,Combinatorics,Real line,Response time,Sample Measure,Time complexity,Segment tree,Mathematics,Kinetic energy
Conference
ISBN
Citations 
PageRank 
1-58113-357-X
7
0.53
References 
Authors
17
3
Name
Order
Citations
PageRank
Mark De Berg11497153.24
João Comba281.22
Leonidas J. Guibas3130841262.73