TY - CHAP
T1 - Smoothed Motion Complexity
AU - Damerow, Valentina
AU - Auf Der Heide, Friedhelm Meyer
AU - Räcke, Harald
AU - Scheideier, Christian
AU - Sohler, Christian
PY - 2003
Y1 - 2003
N2 - We propose a new complexity measure for movement of objects, the smoothed motion complexity. Many applications are based on algorithms dealing with moving objects, but usually data of moving objects is inherently noisy due to measurement errors. Smoothed motion complexity considers this imprecise information and uses smoothed analysis [13] to model noisy data. The input is object to slight random perturbation and the smoothed complexity is the worst case expected complexity over all inputs w.r.t. the random noise. We think that the usually applied worst case analysis of algorithms dealing with moving objects, e.g., kinetic data structures, often does not reflect the real world behavior and that smoothed motion complexity is much better suited to estimate dynamics. We illustrate this approach on the problem of maintaining an orthogonal bounding box of a set of n points in ℝd under linear motion. We assume speed vectors and initial positions from [-1, 1]d. The motion complexity is then the number of combinatorial changes to the description of the bounding box. Under perturbation with Gaussian normal noise of deviation a the smoothed motion complexity is only polylogarithmic: O(d · (1 + 1/σ) · log n3/2) and Ω(d ·√log n). We also consider the case when only very little information about the noise distribution is known. We assume that the density function is monotonically increasing on ℝ≤0 and monotonically decreasing on ℝ≤0 and bounded by some value C. Then the motion complexity is O(√n log n · C + log n) and Ω(d · min{ 5√n/σ, n}). Keywords: Randomization, Kinetic Data Structures, Smoothed Analysis
AB - We propose a new complexity measure for movement of objects, the smoothed motion complexity. Many applications are based on algorithms dealing with moving objects, but usually data of moving objects is inherently noisy due to measurement errors. Smoothed motion complexity considers this imprecise information and uses smoothed analysis [13] to model noisy data. The input is object to slight random perturbation and the smoothed complexity is the worst case expected complexity over all inputs w.r.t. the random noise. We think that the usually applied worst case analysis of algorithms dealing with moving objects, e.g., kinetic data structures, often does not reflect the real world behavior and that smoothed motion complexity is much better suited to estimate dynamics. We illustrate this approach on the problem of maintaining an orthogonal bounding box of a set of n points in ℝd under linear motion. We assume speed vectors and initial positions from [-1, 1]d. The motion complexity is then the number of combinatorial changes to the description of the bounding box. Under perturbation with Gaussian normal noise of deviation a the smoothed motion complexity is only polylogarithmic: O(d · (1 + 1/σ) · log n3/2) and Ω(d ·√log n). We also consider the case when only very little information about the noise distribution is known. We assume that the density function is monotonically increasing on ℝ≤0 and monotonically decreasing on ℝ≤0 and bounded by some value C. Then the motion complexity is O(√n log n · C + log n) and Ω(d · min{ 5√n/σ, n}). Keywords: Randomization, Kinetic Data Structures, Smoothed Analysis
UR - http://www.scopus.com/inward/record.url?scp=0142152744&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-39658-1_17
DO - 10.1007/978-3-540-39658-1_17
M3 - Chapter
AN - SCOPUS:0142152744
SN - 3540200649
SN - 9783540200642
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 161
EP - 171
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - di Battista, Giuseppe
A2 - Zwick, Uri
PB - Springer Verlag
ER -