Two PhD positions in Computational Geometry at Utrecht University

[Marc van Kreveld]

At the Institute of Information and Computing Sciences of Utrecht
University, there are openings for

two PhD students

in computational geometry on a project entitled GOGO:

Geometric Optimization with Geometric Constraints

funded by the Netherlands Organisation for Scientific Research (NWO).
The research will be supervised by dr. Marc van Kreveld and dr. Rene
van Oostrum, and will be done at the Center for Geometry, Imaging and
Virtual Environments (GIVE), headed by prof.dr. Mark Overmars.
See http://www.give.nl/

Summary
-------
Geometric computation for cartography, realistic terrain modeling, and
delineation of imprecise geographic regions all require geometric
algorithms where several geometric criteria must be met simultaneously.
This proposal addresses such computational problems by designing new
algorithms with efficiency analyses and approximation factor proofs.

In cartographic generalization, for example, spatial aggregation of
two regions asks for a new, connected region that has a natural shape,
but while adding as little area in the connection as possible. For
metro maps, stations must be close to their true location, connections
may only have few, restricted-orientation links, and connections may
not intersect. Many other examples can be given in which there are
several criteria that determine a good solution.

In terrain modeling, conversion of an elevation grid to a polyhedral
terrain (triangulation) is an important operation. The resulting
triangulation is often the Delaunay triangulation because it maximizes
the smallest angle used. Therefore, it is good for height interpolation.
But other criteria like slope fidelity and avoiding artificial dams are
also important. These problems will be studied using higher-order
Delaunay triangulations.

Geometric optimization problems are often NP-hard, or an optimal
solution is incomputable. Allowing additional constraints will not
reduce asymptotic running time. Instead, problems will become
essentially more difficult. Therefore, the focus will be on efficient
approximation algorithms with guaranteed performance factors. The
starting point is problems with two geometric constraints where one
constraint must be met using a threshold, while the other constraint
is optimized. The goal is to obtain an understanding to what extent
problems with several geometric criteria can be solved or approximated
efficiently.

We offer
--------
- A position as a PhD student for four years. In the Netherlands,
PhD students are not considered students but research staff.
Hence, they get a (competitive) salary rather than a scholarship.
- An interesting, internationally oriented working environment that
specializes in computational geometry and its applications.
- The possibility to follow courses and attend international
summerschools and conferences.

We look for computer scientists with a Master's degree and
----------------------------------------------------------
- Interest in and good knowledge of algorithms, preferably geometric
algorithms
- Affinity with mathematics
- Interest in applications to the spatial sciences

More information
----------------
Interested candidates can contact dr. M. van Kreveld (Marc),
phone. +31 - 30 - 2534119, e-mail: marc at cs.uu.nl, for a more
extensive project description. Applications consisting of an
application letter and CV can be sent by e-mail to
dr. M. van Kreveld.

-------------
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.