PhD fellowship - Effective computational geometry
Sylvain.Petitjean at loria.fr
Wed Jun 16 19:31:46 PDT 2004
(Please pass to interested parties.)
Applications are invited for a PhD fellowship in the field of effective
computational geometry and geometric computing. The PhD topic is on
efficient calculation of arrangements of quadrics (degree 2 surfaces) --
for more details.
Research will take place at the LORIA laboratory, Nancy, France, in the ISA
project-team (Models, algorithms and geometry for computer graphics and
vision). See the web pages for further info: http://www.loria.fr and
The PhD grant is slightly above 1300 euros per month over 36 months. The
scheduled to start in October 2004.
The ideal candidate will have working knowledge of computational
geometry and a
solid background in mathematics.
The exact conditions to be allowed to apply for this fellowship are
stated on the
following page (in French):
Roughly: to be under 25, to have or be about to have a Master's degree,
to be a
citizen of a member state of the European Union. There are also special
for citizens of Bulgaria, Russia, Iceland, Norway, Roumania, Switzerland and
Turkey, so feel free to send e-mail to enquire.
To apply, please send a fairly complete vitae by e-mail to
Sylvain.Petitjean at loria.fr
The schedule is very tight: deadline for application is set to July 5th,
54506 Vandoeuvre cedex
Efficient and Robust Computation of Arrangements of Quadrics
The two most widely used types of object representation in solid
constructive solid geometry (CSG) and boundary representation (BRep). Both
representations having their own respective advantages, solid modeling
often need an efficient and reliable way to convert one type of
into the other. CSG-to-BRep conversion is a well understood problem, but
approaches have often put more emphasis on efficiency than on robustness and
accuracy. If only finite-precision arithmetic is assumed, the topological
consistency of the compute BRep can easily be jeopardized by small
error introduced in the data. For many applications in design and automated
manufacturing, this may be unacceptable.
Designing reliable and robust algorithms is currently a major interest
computational geometry and geometric computing research communities. A
successful approaches have been proposed for the robust and accurate
conversion of polyhedral models. Computing the topological structure of
involves accurately evaluating signs of arithmetic expressions, which can be
achieved for piecewise-linear models assuming the necessary bit length
for number representation.
By contrast, there has been much less work on robust CSG-to-BRep conversion
algorithms for curved primitives (but see [1,2,3]). A major reason is
the linear realm exact arithmetic computations require algebraic numbers
cannot in general be represented explicitly with a finite number of bits. In
addition, computation with algebraic numbers is extremely slow.
In the algebraic domain, the most simple surfaces, outside piecewise-linear
meshes, are degree 2 surfaces, i.e. quadrics. Quadrics represent a
compromise between complexity, flexibility and modeling power. With
respect to the
CSG-to-BRep conversion problem, and more generally to the computation of
arrangements of quadrics, they also have undeniable advantages. Indeed, the
quadratic nature of their defining equations permits an explicit
intersection curves. Thus, it is theoretically possible to compute a fully
parametric representation of the boundary of second-order CSG solids.
The goal of this PhD is to make strides towards this goal. Recently, we have
proposed and implemented a robust algorithm for the near-optimal
of the intersection of two quadrics [4,5]. The complexity of the output
in terms of the number and depth of the radicals involved. Using this
(and the accompanying theoretical results) as a building block, the doctoral
candidate will propose solutions for the robust and efficient computation of
arrangements of quadrics. Depending on his/her background, he/she will
specifically on one or several of the many different aspects of the problem:
handling degenerate cases, mixing finite-precision and exact arithmetic,
ensuring the geometrical-topological consistency, using filters,
geometric predicates, managing complexity, solving polynomial equations with
algebraic coefficients, sorting algebraic points along a curve, ...
 J. Keyser, S. Krishnan and D. Manocha, Efficient and Accurate BRep
of Low Degree Sculptured Solids Using Exact Arithmetic, Computer Aided
Design, 16 (9), 1999.
 E. Schömer and N. Wolpert, An Exact and Efficient Approach for
Cell in an Arrangement of Quadrics, Computational Geometry: Theory and
 B. Mourrain, J.-P. Técourt and Monique Teillaud, Predicates for the
of an Arrangement of Quadrics in 3D, Computational Geometry: Theory and
 L. Dupont, D. Lazard, S. Lazard and S. Petitjean, Near-Optimal
Parameterization of the Intersection of Quadrics, Proc. of the ACM
Computational Geometry, 2003.
 S. Lazard, L. M. Peñaranda and S. Petitjean, Intersecting Quadrics: An
Efficient and Exact Implementation, Proc. of the ACM Symposium on
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce