Home // ADVCOMP 2011, The Fifth International Conference on Advanced Engineering Computing and Applications in Sciences // View article

On Root Classification in Kinetic Data Structures

Authors:
Tomas Vomacka
Ivana Kolingerova

Keywords: Computational geometry, Polynomials, Data structures.

Abstract:
In this paper we discuss the mathematical properties of kinetic events computation for kinetic data structures with polynomial-type certificate functions. We show that it is neither theoretically possible nor numerically safe to ignore the multiplicities of roots of these equations. The multiplicities of the roots are sometimes ignored in order to speed up the process of estimating their location, however, they must be taken into account during the management of the kinetic data structures. Some of the roots obtained by the computations of these equations do not necessarily carry the expected information (i.e., the times of future kinetic events) and they may be therefore avoided entirely during the computation. This text shows how to distinguish these roots before their exact location is computed and thus to avoid their computation.

Pages: 32 to 36

Copyright: Copyright (c) IARIA, 2011

Publication date: November 20, 2011

Published in: conference

ISSN: 2308-4499

ISBN: 978-1-61208-172-4

Location: Lisbon, Portugal

Dates: from November 20, 2011 to November 25, 2011