LIPIcs.SoCG.2016.33.pdf
- Filesize: 1.08 MB
- 17 pages
Document
Qualitative Symbolic Perturbation
Authors
-
Part of:
Volume:
32nd International Symposium on Computational Geometry (SoCG 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-10
Cite As Get BibTex
Olivier Devillers, Menelaos Karavelas, and Monique Teillaud. Qualitative Symbolic Perturbation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.33
Abstract
In a classical Symbolic Perturbation scheme, degeneracies are handled by substituting some polynomials in epsilon for the inputs of a predicate. Instead of a single perturbation, we propose to use a sequence of (simpler) perturbations. Moreover, we look at their effects geometrically instead of algebraically; this allows us to tackle cases that were not tractable with the classical algebraic approach.
Subject Classification
Keywords
- Robustness issues
- Symbolic perturbations
- Apollonius diagram
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- P. Alliez, O. Devillers, and J. Snoeyink. Removing degeneracies by perturbing the problem or the world. Reliable Computing, 6:61-79, 2000. URL: http://hal.inria.fr/inria-00338566/.
- H. Brönnimann, O. Devillers, V. Dujmović, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides. Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra. SIAM Journal on Computing, 37:522-551, 2007. URL: http://hal.inria.fr/inria-00103916.
- C. Burnikel, K. Mehlhorn, and S. Schirra. On degeneracy in geometric computations. In 5th ACM-SIAM Sympos. Discrete Algorithms, pages 16-23, 1994. URL: http://dl.acm.org/citation.cfm?id=314474.
- O. Devillers, M. Glisse, and S. Lazard. Predicates for line transversals to lines and line segments in three-dimensional space. In Proc. 24th Annual Symposium on Computational Geometry, pages 174-181, 2008. URL: http://hal.inria.fr/inria-00336256/.
- O. Devillers, M. Karavelas, and M. Teillaud. Qualitative symbolic perturbation: two applications of a new geometry-based perturbation framework. Research Report 8153, INRIA, 2015. version 4. URL: http://hal.inria.fr/hal-00758631/.
- O. Devillers and M. Teillaud. Perturbations for Delaunay and weighted Delaunay 3D triangulations. Computational Geometry: Theory and Applications, 44:160-168, 2011. URL: http://dx.doi.org/10.1016/j.comgeo.2010.09.010.
- H. Edelsbrunner and E. P. Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph., 9(1):66-104, 1990. URL: http://dl.acm.org/citation.cfm?id=77639.
- I. Emiris and J. Canny. A general approach to removing degeneracies. SIAM J. Comput., 24:650-664, 1995. URL: http://epubs.siam.org/sicomp/resource/1/smjcat/v24/i3/p650_s1.
- I. Emiris and M. Karavelas. The predicates of the Apollonius diagram: algorithmic analysis and implementation. Computational Geometry: Theory and Applications, 33(1-2):18-57, January 2006. URL: http://dx.doi.org/10.1016/j.comgeo.2004.02.006.
- G. Irving and F. Green. A deterministic pseudorandom perturbation scheme for arbitrary polynomial predicates. Technical Report 1308.1986v1, arXiv, 2013. URL: http://arxiv.org/abs/1308.1986.
- K. Mehlhorn, R. Osbild, and M. Sagraloff. A general approach to the analysis of controlled perturbation algorithms. Comput. Geom. Theory Appl., 44:507-528, 2011. URL: http://dx.doi.org/10.1016/j.comgeo.2011.06.001.
-
R. Seidel. The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom., 19:1-17, 1998.
- R. Seidel. Perturbations in geometric computing, 2013. Workshop on Geometric Computing, Heraklion. URL: http://www.acmac.uoc.gr/GC2013/files/Seidel-slides.pdf.
- C. K. Yap. A geometric consistency theorem for a symbolic perturbation scheme. J. Comput. Syst. Sci., 40(1):2-18, 1990. URL: http://www.sciencedirect.com/science/article/pii/002200009090016E.
- C. K. Yap. Symbolic treatment of geometric degeneracies. J. Symbolic Comput., 10:349-370, 1990. URL: http://www.sciencedirect.com/science/article/pii/S0747717108800697.
- C. K. Yap and T. Dubé. The exact computation paradigm. In Computing in Euclidean Geometry, volume 4 of Lecture Notes Series on Computing, pages 452-492. World Scientific, 1995. URL: http://www.cs.nyu.edu/~exact/doc/paradigm.ps.gz.