Hervé Brönnimann's Research Interests

Computational Geometry
Range searching
Derandomization of geometric algorithms
Numerical Problems in Computational Geometry
CGAL: A Library of Geometric Algorithms
REFERENCES

Computational geometry

Computational geometry is a well-established topic in theoretical computer science, introduced as a field for the first time in M.I. Shamos' thesis. Within its scope lie the analysis of combinatorial geometric objects and the design and analysis of algorithms that compute them. Starting from problems in graphics, robotics, CAD/CAM, the community has abstracted basic problems, structures, and primitives that could model them; a set of techniques have been developed which is now exposed in many of many books.^,^,^,^, The topics covered are numerous and have many cross-connections; among them, one should mention: arrangements (lines, segments, circles and arcs, planes, triangles, spheres, and more generally algebraic objects), intersection detection and computation (of polygons, segments, polyhedra, spheres), distance/proximity problems (Voronoi diagrams, diameter, closest pair and collision detection), geometric optimization (facility location, covering/packing, small-dimensional linear programming), and multidimensional sorting (convex hulls, point arrangements, range searching). Below, I mention a few problems I was able to contribute to.

Range searching

Range searching aims at preprocessing points of ${\mathbb R}^d$ in a given population in order to answer efficiently queries in a given range. Many database searches can be expressed in this framework: the query consists of finding the points in a given region (usually a half-space, a simplex, or an axis-aligned paralletope). Many solutions are proposed in the litterature. For triangles in the plane, the best solutions, given n point and preprocessing space m=O(n²), answer any query in time $O(n/\sqrt{m})$ . It turns out that this is optimal for the worst query: there is a matching lower bound (it can be extended to any dimension). Even more, the lower bound applies to the average query time. Lower bounds such as these are difficult to come by and few techniques have been given to establish them.^,^,^, None of these lower bounds applies to half-spaces, and Chazelle and I brought a further contribution by providing the first lower bound in this case [3,9]. For instance, for triangles in the plane, we obtain the lower bound on the average query time of $\Omega(n^{5/6}/\sqrt{m})$ . This case is important as any algebraic query reduces to it by linearization.

Derandomization of geometric algorithms

For the past ten years, optimal randomized solutions have been given to the basic problems: by making random choices during their execution, these algorithms achieve an asymptotically optimal average running time. In some cases, they even are the only known optimal algorithms (e.g., for the diameter problem in ${\mathbb R}^3$ ). Their analysis may be involved, still they are usually easy to implement and to extend. For instance, the incremental algorithms can be made dynamic (on-line deletions) with little complication. The randomized segment intersection algorithms also work for curves with a constant number of intersections.

Deterministic algorithms, however, are harder to obtain. The first asymptotically optimal segment intersection algorithm is certainly more involved than its earlier randomized counterparts.^, In some rare instances, deterministic algorithms offer better asymptotic performance than randomized ones (for polygon triangulation for instance). Nevertheless, randomized algorithms are more practical.

Therefore, to take advantage of the properties of randomized algorithms, I am interested in derandomized algorithms. These are obtained from randomized ones by ``computing random choices'' in a way that satisfies the properties that make randomized algorithms efficient. A number of these properties can be modeled by set systems. In all the randomized algorithms mentioned above, the set systems have finite VC-dimension.This guarantees that there exist small samples representative of the whole set system, which provide statistical information about the problem. Matousek, Chazelle, and I have shown can compute such samples ( $\varepsilon$ -nets and approximations) efficiently [1,6,10], and use the gained information to mimick the average behavior of the randomized algorithms, but without performing any random choice. Among applications of this general technique, we mention [1,6,10] the only deterministic algorithm that is optimal in the worst case and in any dimension, to compute the convex hull of n points in ${\mathbb R}^d$ . (It is a simpler version of Chazelle's algorithm; moreover, the latter requires that $d\geq 4$ .) The techniques can also derandomize other geometric algorithms without increasing the running time by more than a constant factor: with Goodrich, I devised an algorithm that finds, between nested convex polyhedra, one with an almost minimum number of facets [4,11] (to find the minimum is NP-hard); with Chazelle, I gave an algorithm that finds the connecting line of a set of points with the median slope [5,12], a quantity called Theil-Senn estimator by statisticians.

Only very recently have studies addressed practical issues, such as the constants involved.It would be interesting to see how practical these methods can be, but also how they can in turn influence the implementation of randomized algorithms (for instance, by suggesting a score function on randomized insertions).

Numerical Problems in Computational Geometry

Geometric algorithms are notorious for suffering from robustness problems. Even a simple problem like computing the intersecting pairs among a set of segments in the plane is difficult to implement correctly, which prompted many to ignore this problem in implementing geometric algorithms. As a result, most of the geometric programs available on the internet, or even commercially, do not address this problem.

Much research has focused recently on improving this situation within the community.^,^,Starting with the work by Clarkson,we developped a battery of tools to obtain exact geometric predicates [7,8,13,14,15,16]. The techniques used range from basic linear algebra to sign computation in residue number systems. In particular, with Victor Pan and Ioannis Emiris, I designed a fast implementation of determinant sign evaluation [8,14,15] by using modular arithmetic, which is the most efficient method known to date. The code, written by my student Sylvain Pion, is available and will be applied in as various areas as computational geometry, symbolic algebra (Sturm sequences, resultant theory), and numerical software design.

These exact methods suffer from a loss of performance, but we can adjoin geometric filters, introduced by Fortune and van Wyk: their efficiency is within a constant factor of straight floating point evaluation, and they provide a certification in likely case of success. In numerically difficult cases, they fail, and the more expensive exact predicates must be used. The efficiency of filters relies on the high probability of success. Burnikel, Pion, and I also developed efficient filters (both fast and with respect to efficiency) for numerically more demanding geometric predicates, such as high order determinants [16].

We plan to bundle these tools in a package for the CGAL library so that geometric computation, both efficient and robust, will be made available to the community.

A Library of Geometric Algorithms

Many areas of computing have a common platform for experimenting and prototyping. There is CPLEX for linear programming, MAPLE and MATHEMATICA for symbolic computing, MATLAB, LAPACK and EISPACK for numerical computing, BIOSYM for chemistry and molecular modeling, and LEDA for data types and combinatorial algorithms. By contrast, there is no library of geometric types and algorithms. The reasons for this are partially given in the preceding paragraph: geometric algorithms are extremely difficult to code because of robustness problems. Also, many of the algorithms in the litterature are not specified at the level of reusable software components, making them hard to integrate in a library.

I believe that the entire community would benefit from a library for geometric computing. There are many profits to be reaped from such a platform. For instance, rapid prototypes could be developed, and ideas tested easily by reusing the kernel objects. Algorithms could be experimentally compared without the bias of different languages and primitives, making practical studies more fair and meaningful. Also, communication of code would be improved within and beyond the community.

Seven European academic sites, including INRIA Sophia-Antipolis, have started a project called CGAL aimed at providing such a platform. Although I was not yet a member of INRIA when it started, I have been actively involved and became Technical Project Manager. I am responsible for maintaining the code produced at INRIA and for developing new packages for the library. This includes Cartesian Kernel classes (there are also homogeneous representations), interface with various visualisation softwares, Delaunay and constrained triangulations (2D and 3D).

This collaboration will continue in the future.