ARC Arcadia

(INRIA Cooperative Research Initiative, 2005-2006)

Arrangements of quadrics, algorithms,
implementation and applications

Goals

Scientific objectives

The main objective of this ARC is to contribute to the unfolding of a geometric computing dedicated to quadrics having solid mathematical foundations and to validate theoretical advances by robust and efficient implementations.

See the ARC proposal (restricted access).

Members

The members of the ARC Arcadia are spread across three different places:

INRIA Sophia-Antipolis, Geometrica research team
- Sylvain Pion, researcher, INRIA
- Daniel Russel, postdoctoral fellow (apr-sept 2006)
- Monique Teillaud, researcher, INRIA
- Elias Tsigaridas, postdoctoral fellow (oct-dec 2006)
INRIA Lorraine, ISA/Vegas research team
- Laurent Dupont, lecturer, University of Nancy 2
- Sylvain Lazard, researcher, INRIA
- Luis M. Peñaranda, PhD student
- Maria Pentcheva, PhD student
- Sylvain Petitjean, researcher, CNRS
- Elias Tsigaridas, postdoctoral fellow (jan-sept 2007)
Laboratory of Geometric & Algebraic Algorithms, Department of Informatics, National University of Athens
- Ioannis Emiris, associate professor
- Menelaos Karavelas, assistant professor, Department of Applied Mathematics, University of Crete
- Elias Tsigaridas, PhD student
- George Tzoumas, PhD student

Meetings

January, 2007: Elias Tsigaridas continues his postdoc at Loria.

November, 2006: Two new techreports: A note on the complexity of univariate root isolation (Emiris, Tsigaridas) et On the complexity of real root isolation using continued fractions (Tsigaridas, Emiris).

September, 2006: Elias Tsigaridas starts his postdoc at INRIA Sophia.

October 17-18, 2006: Journées nationales des ARC, INRIA Rhône-Alpes. Our slides are here (restricted).

September 5-8, 2006: Monique Teillaud visits Loria.

September 5-6, 2006: Daniel Russel visits Loria. He gives a talk on arrangements of spheres.

July 17-21, 2006: Luis M. Peñaranda visits Monique Teillaud at INRIA Sophia Antipolis.

March 20-24, 2006: Second Arcadia Workshop, National University of Athens.

October 18-28, 2005: Arcadia meeting, INRIA Sophia-Antipolis, on the specifications of the curved kernel and related topics.
Participants: Menelaos Karavelas, Sylvain Pion, Monique Teillaud, Elias Tsigaridas.

September 5-9, 2005: Arcadia meeting, Loria, on projective structures and extensions to the projective domain of classical concepts and algorithms like arrangements, triangulations, sweep algorithms, ...
Participants: Laurent Dupont, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Théo Papadopoulo, Sylvain Petitjean, Jean Ponce, Monique Teillaud.

June 27-July 1, 2005: First Arcadia Workshop, Loria-Saint Fiacre.

April 6, 2005: Wenping Wang visits Loria.

March 31-April 1, 2005: Laurent Dupont and Sylvain Lazard participate in the Quadric Day, INRIA Sophia-Antipolis.

March 21-25, 2005: Monique Teillaud visits Loria.

Publications

O. Devillers, A. Fronville, B. Mourrain, and M. Teillaud, Algebraic methods and arithmetic filtering for exact predicates on circle arcs, Computational Geometry: Theory and Applications, 22:119-142, 2002.
L. Dupont, D. Lazard, S. Lazard, and S. Petitjean, Near-optimal parameterization of the intersection of quadrics, in Proc. of ACM Symposium on Computational Geometry, pages 246-255, 2003.
I. Emiris, A. Kakargias, S. Pion, M. Teillaud, and E. Tsigaridas, Towards an open curved kernel, in Proc. of 20th Annual ACM Symposium on Computational Geometry, pages 438-446, 2004.
I. Emiris and E. Tsigaridas, Comparing with real algebraic numbers of small degree, in Proc. of European Symposium on Algorithms, pages 652-663, 2004.
I. Emiris and E. Tsigaridas, Real Solving of Bivariate Polynomial Systems, in Proc. of International Workshop on Computer Algebra in Scientific Computing, Lecture Notes in Computer Science, 2005.
M. Karavelas and I. Emiris, Root comparison techniques applied to computing the additively weighted Voronoi diagram, in Proc. of 14th ACM-SIAM Symposium on Discrete Algorithms, pages 320-329, 2003.
S. Lazard, L. M. Peñaranda, and S. Petitjean, Intersecting quadrics: An efficient and exact implementation, in Proc. of ACM Symposium on Computational Geometry, pages 419-428, 2004.
S. Lazard, L. M. Peñaranda, and S. Petitjean, Intersecting quadrics: An efficient and exact implementation, Computational Geometry: Theory and Applications, to appear.
C. Li, S. Pion, and C. Yap, Recent progress in exact geometric computation, Journal of Logic and Algebraic Programming, 2004. Special issue on the practical development of exact real number computation, to appear.
B. Mourrain, J.-P. Técourt, and M. Teillaud, On the Computation of an Arrangement of Quadrics in 3D, Computational Geometry: Theory and Applications, 30:145-164, 2005. Special issue, 19th European Workshop on Computational Geometry.
I. Emiris, G. Tzoumas and E. Tsigaridas The Predicates for the Voronoi Diagram of Ellipses, Proc. of ACM Symposium on Computational Geometry, 2006.

Software

CGAL (Computational Geometry Algorithms Library)

QI (Exact parameterization of the intersection of quadrics)

Webmaster
Last modified: Sep 5 2006