PhD fellowship - Effective computational geometry

Sylvain Petitjean Sylvain.Petitjean at
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 
robust and
efficient calculation of arrangements of quadrics (degree 2 surfaces) -- 
see below
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: and

The PhD grant is slightly above 1300 euros per month over 36 months. The 
thesis is
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

The schedule is very tight: deadline for application is set to July 5th, 

Contact person:

Sylvain Petitjean
Campus scientifique
BP 239
54506 Vandoeuvre cedex


Efficient and Robust Computation of Arrangements of Quadrics

The two most widely used types of object representation in solid 
modeling are
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 
amounts of
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 
of the
computational geometry and geometric computing research communities. A 
number of
successful approaches have been proposed for the robust and accurate 
conversion of polyhedral models. Computing the topological structure of 
a BRep
involves accurately evaluating signs of arithmetic expressions, which can be
achieved for piecewise-linear models assuming the necessary bit length 
is allowed
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 
that outside
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 
fairly good
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 
representation of
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 
is minimal
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 
focus more
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, 
designing proper
geometric predicates, managing complexity, solving polynomial equations with
algebraic coefficients, sorting algebraic points along a curve, ...

[1] 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.

[2] E. Schömer and N. Wolpert, An Exact and Efficient Approach for 
Computing a
Cell in an Arrangement of Quadrics, Computational Geometry: Theory and
Applications, 2004.

[3] B. Mourrain, J.-P. Técourt and Monique Teillaud, Predicates for the 
of an Arrangement of Quadrics in 3D, Computational Geometry: Theory and
Applications, 2004.

[4] L. Dupont, D. Lazard, S. Lazard and S. Petitjean, Near-Optimal
Parameterization of the Intersection of Quadrics, Proc. of the ACM 
Symposium on
Computational Geometry, 2003.

[5] S. Lazard, L. M. Peñaranda and S. Petitjean, Intersecting Quadrics: An
Efficient and Exact Implementation, Proc. of the ACM Symposium on 
Geometry, 2004

	- Sylvain

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list