Files:DescriptionFile size FormatBrowse
Fulltext0.84 MBPDF (requires Acrobat Reader)Previous | Next
  
Authors:Tomáš Vomácka: University of West Bohemia, Czech Republic
Ivana Kolingerová: University of West Bohemia, Czech Republic
Publication title:Computation of Topologic Events in Kinetic Delaunay Triangulation using Sturm Sequences of Polynomials
Conference:SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27–28; 2008 Stockholm; Sweden
Publication type: Abstract and Fulltext
Issue:034
Article No.:014
Abstract:Even though the problem of maintaining the kinetic Delaunay triangulation is well known; this field of computational geometry leaves several problems unsolved. We especially aim our research at the area of computing the times of the topologic events. Our method uses the Sturm sequences of polynomials which; combined together with the knowledge in associated field of mathematics; allows us to separate the useful roots of the counted polynomial equations from those which are unneeded. Furthermore; we adress the problem of redundant event computation which consumes an indispensable amount of the runtime (almost 50% of the events is computed but not executed). Despite the deficiency in the fields of speed and stability of our current implementation of the algorithm; we show that a large performance enhancement is theoreticaly possible by recognizing and not computing the redundant topologic events.

CR Categories: G.1.5 [Numerical Analysis]: Roots of Nonlinear Equations—Polynomials; methods for; I.3.5 [Computer Graphics]: Computational Geometry and Object Modelling—Geometric algorithms; languages; and systems

Language:English
Keywords:Kinetic Delaunay Triangulation; Polynomial; Sturm Sequence
Year:2008
No. of pages:8
Pages:57-64
Series:Linköping Electronic Conference Proceedings
ISSN (print):1650-3686
ISSN (online):1650-3740
File:http://www.ep.liu.se/ecp/034/014/ecp083414.pdf
Available:2008-11-27
Publisher:Linköping University Electronic Press; Linköpings universitet

REFERENCE TO THIS PAGE
Tomáš Vomácka, Ivana Kolingerová (2008). Computation of Topologic Events in Kinetic Delaunay Triangulation using Sturm Sequences of Polynomials, SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27–28; 2008 Stockholm; Sweden http://www.ep.liu.se/ecp_article/index.en.aspx?issue=034;article=014 (accessed 10/31/2014)