| Files: | Description | File size | Format | Browse |
| Fulltext | 0.84 MB | PDF (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 5/18/2013) |
|
Ph.D., Lic. Theses
