PhD fellowship - Effective computational geometry

[Sylvain Petitjean]

(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 
artificial
vision). See the web pages for further info: http://www.loria.fr and
http://www.loria.fr/isa

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):

   http://dr.education.fr/Alloc_doc/alloc_2.html

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 
conditions
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, 
2004.

Contact person:

Sylvain Petitjean
LORIA
Campus scientifique
BP 239
54506 Vandoeuvre cedex
FRANCE

-----------------

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 
kernels
often need an efficient and reliable way to convert one type of 
representation
into the other. CSG-to-BRep conversion is a well understood problem, but 
past
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 
CSG-to-BRep
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 
which
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 
parameterization
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 
algorithm
(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 
Generation
of Low Degree Sculptured Solids Using Exact Arithmetic, Computer Aided 
Geometric
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 
Sweeping
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 
Computational
Geometry, 2004

-- 
	- Sylvain



-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.