Document Open Access Logo

Qualitative Symbolic Perturbation

Authors Olivier Devillers, Menelaos Karavelas, Monique Teillaud

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2016.33.pdf
  • Filesize: 1.08 MB
  • 17 pages

Document Identifiers

Subject Classification

Keywords
  • Robustness issues
  • Symbolic perturbations
  • Apollonius diagram

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

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

Author Details

Olivier Devillers
Menelaos Karavelas
Monique Teillaud

References

  1. 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/.
  2. 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.
  3. 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.
  4. 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/.
  5. 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/.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. R. Seidel. The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom., 19:1-17, 1998. Google Scholar
  13. R. Seidel. Perturbations in geometric computing, 2013. Workshop on Geometric Computing, Heraklion. URL: http://www.acmac.uoc.gr/GC2013/files/Seidel-slides.pdf.
  14. 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.
  15. C. K. Yap. Symbolic treatment of geometric degeneracies. J. Symbolic Comput., 10:349-370, 1990. URL: http://www.sciencedirect.com/science/article/pii/S0747717108800697.
  16. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact