Search

We describe an algorithm which, for any piecewise linear complex (PLC) in 3D, builds a Delaunay triangulation conforming to this PLC. The algorithm has been implemented, and yields in practice a relatively small number of Steiner points due to the fact that it adapts to the local geometry of the PLC. It is, to our knowledge, the first practical algorithm devoted to this problem.

In this paper, we show that, amongst $n$ uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176--206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and accommodates non-uniform samples. The reconstructed surface interpolates the data points and is implicitly represented as the zero set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound, which makes the method especially relevant for small point sets. Experimental results are presented for surfaces in R3.

International audience; Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an exact and efficient method that determines the sign of a multivariate polynomial expression with rational coefficients. Exactness is achieved by using modular computation. Although this usually requires some multiprecision computation, our novel techniques of recursive relaxation of the moduli and their variants enable us to carry out sign determination and comparisons by using only single precision. Moreover, to exploit modern day hardware, we exclusively rely on floating point arithmetic, which leads us to a hybrid symbolic-numeric approach to exact arithmetic. We show how our method can be used to generate robust and efficient implementations of real algebraic and geometric algorithms including Sturm sequences, algebraic representation of points and curves, convex hull and Voronoi diagram computations and solid modeling. This method is highly parallelizable, easy to implement, and compares favorably with known multiprecision methods from a practical complexity point of view. We substantiate these claims by experimental results and comparisons to other existing approaches.

International audience; Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his velocity. The problem we address is how to preprocess the postmen data so as to be able to efficiently answer two types of nearest-neighbor queries. The first one asks ``who is the nearest postman at time tq to a dog located at point sq. In the second type a query dog is located at point sq at time tq, its speed is vq>|vi| (for all i=1, ... , n), and we want to know which postman the dog can catch first. The first type of query is relatively simple to address, the second type at first seems much more complicated. We show that the problems are very closely related, with efficient solutions to the first type of query leading to efficient solutions to the second. We then present two solutions to these problems, with tradeoff between preprocessing time and query time. Both solutions use deterministic data structures.

International audience; This paper is not a complete survey on randomized algorithms in computational geometry, but an introduction to this subject providing intuitions and references. In a first time, some basic ideas are illustrated by the sorting problem, and in a second time few results on computational geometry are briefly explained.

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region R α (S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of R α (S) is O( n α 5 ) . Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

This paper deals with the approximation of the unfolding of a smooth globally developable surface (i.e. "isometric" to a domain of ${\Bbb E}^2$) with a triangulation. We prove the following result: let Tn be a sequence of globally developable triangulations which tends to a globally developable smooth surface S in the Hausdorff sense. If the normals of Tn tend to the normals of S, then the shape of the unfolding of Tn tends to the shape of the unfolding of S. We also provide several examples: first, we show globally developable triangulations whose vertices are close to globally developable smooth surfaces; we also build sequences of globally developable triangulations inscribed on a sphere, with a number of vertices and edges tending to infinity. Finally, we also give an example of a triangulation with strictly negative Gauss curvature at any interior point, inscribed in a smooth surface with a strictly positive Gauss curvature. The Gauss curvature of these triangulations becomes positive (at each interior vertex) only by switching some of their edges.

International audience; This paper proposes a new method for isotropic remeshing of tri- angulated surface meshes. Given a triangulated surface mesh to be resampled and a user-specified density function defined over it, we first distribute the desired number of samples by generalizing error diffusion, commonly used in image halftoning, to work directly on mesh triangles and feature edges. We then use the resulting sam- pling as an initial configuration for building a weighted centroidal Voronoi tessellation in a conformal parameter space, where the specified density function is used for weighting. We finally create the mesh by lifting the corresponding constrained Delaunay trian- gulation from parameter space. A precise control over the sampling is obtained through a flexible design of the density function, the latter being possibly low-pass filtered to obtain a smoother grada- tion. We demonstrate the versatility of our approach through vari- ous remeshing examples.

This paper addresses the point-wise estimation of differential properties of a smooth manifold $S$ ---a curve in the plane or a surface in $3D$--- assuming a point cloud sampled over $S$ is provided. The method consists of fitting the local representation of the manifold using a jet, and either interpolation or approximation. A jet is a truncated Taylor expansion, and the incentive for using jets is that they encode all local geometric quantities ---such as normal, curvatures, extrema of curvature. On the way to using jets, the question of estimating differential properties is recasted into the more general framework of multivariate interpolation / approximation, a well-studied problem in numerical analysis. On a theoretical perspective, we prove several convergence results when the samples get denser. For curves and surfaces, these results involve asymptotic estimates with convergence rates depending upon the degree of the jet used. For the particular case of curves, an error bound is also derived. To the best of our knowledge, these results are among the first ones providing accurate estimates for differential quantities of order three and more. On the algorithmic side, we solve the interpolation/approximation problem using Vandermonde systems. Experimental results for surfaces of $\Rn^3$ are reported. These experiments illustrate the asymptotic convergence results, but also the robustness of the methods on general Computer Graphics models.

SIGGRAPH 2003 Session : Surfaces. Article dans revue scientifique avec comité de lecture. internationale.; International audience; In this paper, we propose a novel polygonal remeshing technique that exploits a key aspect of surfaces: the intrinsic anisotropy of natural or man-made geometry. In particular, we use curvature directions to drive the remeshing process, mimicking the lines that artists themselves would use when creating 3D models from scratch. After extracting and smoothing the curvature tensor field of an input geometry patch, lines of minimum and maximum curvatures are used to determine appropriate edges for the remeshed version in anisotropic regions, while spherical regions are simply point-sampled since there is no natural direction of symmetry locally. As a result our technique generates polygon meshes mainly composed of quads in anisotropic regions, and of triangles in spherical regions. Our approach provides the flexibility to produce meshes ranging from isotropic to anisotropic, from coarse to dense, and from uniform to curvature adapted.

International audience; Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T) using constrained Delaunay triangulation. We show that this minimal set is precisely the set of non locally Delaunay edges, and that its cardinality is less than or equal to n+i/2 (if i is the number of interior points in T), which is a tight bound.

Article dans revue scientifique avec comité de lecture.; International audience; In this paper, we consider the problem of computing shortest paths of bounded curvature amidst obstacles in the plane. More precisely, given two prescribed initial and final configurations (specifying the location and the direction of travel) and a set of obstacles in the plane, we want to compute a shortest $C^1$ path joining those two configurations, avoiding the obstacles, and with the further constraint that, on each $C^2$ piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles (as introduced by Agarwal et al.) and present a polynomial-time exact algorithm to solve this problem.

International audience; The compression of geometric structures is a relatively new field of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following approach: the vertices of the mesh are coded in an order that partially contains the topology of the mesh. In the same time, some simple rules attempt to predict the position of each vertex from the positions of its neighbors that have been previously coded. In this article, we describe a compression algorithm whose principle is completely different: the coding order of the vertices is used to compress their coordinates, and then the topology of the mesh is reconstructed from the vertices. This algorithm achieves compression ratios that are slightly better than those of the currently available algorithms, and moreover, it allows progressive and interactive transmission of the meshes.

Encoders for triangle mesh connectivity based on enumeration of vertex valences are among the best reported to date. They are both simple to implement and report the best compressed file sizes for a large corpus of test models. Additionally they have recently been shown to be near-optimal since they realize the Tutte entropy bound for all planar triangulations. In this paper we introduce a connectivity encoding method which extends these ideas to 2-manifold meshes consisting of faces with arbitrary degree. The encoding algorithm exploits duality by applying valence enumeration to both the primal and the dual mesh in a symmetric fashion. It generates two sequences of symbols, vertex valences, and face degrees, and encodes them separately using two context-based arithmetic coders. This allows us to exploit vertex or face regularity if present. When the mesh exhibits perfect face regularity (e.g., a pure triangle or quad mesh) or perfect vertex regularity (valence six or four respectively) the corresponding bit rate vanishes to zero asymptotically. For triangle meshes, our technique is equivalent to earlier valence-driven approaches. We report compression results for a corpus of standard meshes. In all cases we are able to show coding gains over earlier coders, sometimes as large as 50%. Remarkably, we even slightly gain over coders specialized to triangle or quad meshes. A theoretical analysis reveals that our approach is near-optimal as we achieve the Tutte entropy bound for arbitrary planar graphs of two bits per edge in the worst case.

Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in these applications begin by constructing the three-dimensional Delaunay triangulation of a finite set of points scattered over a surface. Their running-time therefore depends on the complexity of the Delaunay triangulation of such point sets. Although the Delaunay triangulation of points in ^3 can be quadratic in the worst-case, we show that, under some mild sampling condition, the complexity of the 3D Delaunay triangulation of points distributed on a fixed number of facets of ^3 (e.g. the facets of a polyhedron) is linear. Our bound is deterministic and the constants are explicitly given.

Numerical simulations take a bigger importance in medical activity as they allow to obtain information non-invasively. To take into account individual variability, we propose numerical simula- tions in geometries reconstructed from medical images. We present the necessary treatment of images of diseased vessels, to provide a computational mesh of an anatomical model of the subject. First a faceted surface is extracted from the images. Then this surface is transformed into a geometrical model to be finally remeshed for a finite element use. Resume .L es simulations numeriques ayant trait au biomedical prennent de plus en plus d'importance car elles permettent d'obtenir de nouvelles informations impossiblesmesurer de maniere non-invasive chez les patients. Pour prendre en compte la variabilite inter-sujet, nous proposons des simulations numeriques dans des getries reconstruitespartir de l'imagerie medicale. Dans la suite, nous presentons le traitement d'images de vaisseaux malades, necessairel'obtention d'un maillage de calcul du modele anatomique du patient. En premier lieu, on extrait des images un ensemble de facettes representant une surface. Puis cette surface est transformee en un modele geometrique qui est finalement remaille pour satisfaire les contraintes d'un maillageements finis.

Given a finite set of points [Formula: see text] in ℝd, the diameter of [Formula: see text] is defined as the maximum distance between two points of [Formula: see text]. We propose a very simple algorithm to compute the diameter of a finite set of points. Although the algorithm is not worst-case optimal, an extensive experimental study has shown that it is extremely fast for a large variety of point distributions. In addition, we propose a comparison with the recent approach of Har-Peled5 and derive hybrid algorithms to combine advantages of both approaches.

International audience; The purpose of this paper is to present a new method to de- sign exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the com- parison of the abscissae of two intersection points of circle arcs, which is known to be a difficult predicate involved in the computation of arrangements of circle arcs. We present an algorithm for deciding the x-order of intersections from the signs of the coefficients of a polynomial, obtained by a general approach based on resultants. This method allows the use of efficient arithmetic and filtering techniques lead- ing to fast implementation as shown by the experimental results.

International audience; Computational geometry classically assumes real-number arithmetic which does not exist in actual computers. A solution consists in using integer coordinates for data and exact arithmetic for computations. This approach implies that if the results of an algorithm are the input of another, these results must be rounded to match this hypothesis of integer coordinates. In this paper, we treat the case of two-dimensional Voronoi diagrams and are interested in rounding the Voronoi vertices to grid points while interesting properties of the Voronoi diagram are preserved. These properties are the planarity of the embedding and the convexity of the cells. We give a condition on the grid size to ensure that rounding to the nearest grid point preserves the properties. We also present heuristics to round vertices (not to the nearest grid point) and preserve these properties.

A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased while still separating the two given sets. An Theta(n log n) optimal algorithm is proposed to find all largest circles separating two given sets of line segments when line segments are allowed to meet only at their endpoints. In the general case, when line segments may intersect $\Omega(n^2)$ times, our algorithm can be adapted to work in O(n alpha(n) log n) time and O(n \alpha(n)) space, where alpha(n) represents the extremely slowly growing inverse of the Ackermann function., Comment: 14 pages, 3 figures, abstract presented at 8th Canadian Conference on Computational Geometry, 1996

International audience; This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for various types of planar subdivisions, such as triangulations, Delaunay triangulations, and convex subdivisions. Their performance is analyzed also in terms of the algorithmic degree, which characterizes the arithmetic precision required.

CGAL is a Computational Geometry Algorithms Library written in C++, which is developed in an ESPRIT LTR project. The goal is to make the large body of geometric algorithms developed in the field of computational geometry available for industrial application. In this chapter we discuss the major design goals for CGAL, which are correctness, flexibility, ease-of-use, efficiency, and robustness, and present our approach to reach these goals. Templates and the relatively new generic programming play a central role in the architecture of CGAL. We give a short introduction to generic programming in C++, compare it to the object-oriented programming paradigm, and present examples where both paradigms are used effectively in CGAL. Moreover, we give an overview on the current structure of the library and consider software engineering aspects in the CGAL-project.

International audience; We discuss floating-point filters as a means of restricting the precision needed for arithmetic operations while still computing the exact result. We show that interval techniques can be used to speed up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding modes of the widely used IEEE 754 standard. Using this approach we engineer an efficient floating-point filter for the computation of the sign of a determinant that works for arbitrary dimensions. We validate our approach experimentally, comparing it with other static, dynamic and semi-static filters.

We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to two constraints: each leg has a maximal extension R (accessibility constraint) and the body of the robot must lie above the convex hull of its feet (stability constraint). Moreover, the robot can only put its feet on some regions, called the foothold regions. The free space F is the set of positions of the body of the robot such that there exists a set of accessible footholds for which the robot is stable. We present an efficient algorithm that computes F in O(n2 log n) time using O(n2 alpha(n)) space for n discrete point footholds where alpha(n) is an extremely slowly growing function (alpha(n), 29 pages, 22 figures, prelininar results presented at WAFR94 and IEEE Robotics & Automation 94

We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric algorithms depends. Our method relies on modular computations, for which comparisons are usually thought to require multiprecision. Our novel technique of {\it recursive relaxation of the moduli} enables us to carry out sign determination and comparisons by using only floating point computations in single precision. This leads us to propose a hybrid symbolic-numeric approach to exact arithmetic. The method is highly parallelizable and is the fastest of all known multiprecision methods \from a complexity point of view. As an application, we show how to compute a few geometric predicates that reduce to matrix determinants and we discuss implementation efficiency, which can be enhanced by arithmetic filters. We substantiate these claims by experimental results and comparisons to other existing approaches. Our method can be used to generate robust and efficient implementations of geometric algorithms (convex hulls, Delaunay triangulations, arrangements) and numerical computer algebra (algebraic representation of curves and points, symbolic perturbation, Sturm sequences and multivariate resultants).

International audience; This note combines the lazy randomized incremental construction scheme with the technique of ``connectivity acceleration'' to obtain an O( (n log*n)^2) time randomized algorithm to compute a single face in the overlay of two simple polygons in the plane.

Let S be a set of n points in the plane. We study the following problem: Partition S by a line into two subsets Sa and Sb such that max{f(Sa), f(Sb)} is minimal, where f is any monotone function defined over 2S. We first present a solution to the case where the points in S are the vertices of a convex polygon and apply it to some common cases — f(S′) is the perimeter, area, or width of the convex hull of S′⊆S — to obtain linear solutions (or O(n log n) solutions if the convex hull of S is not given) to the corresponding problems. This solution is based on an efficient procedure for finding a minimal entry in matrices of some special type, which we believe is of independent interest. For the general case we present a linear space solution which is in some sense output sensitive. It yields solutions to the perimeter and area cases that are never slower and often faster than the best previous solutions.

Finding a vast array of applications, the list-ranking problem has emerged as one of the fundamental techniques in parallel algorithm design. Surprisingly, the best previously known algorithm to rank a list of n items on a reconfigurable mesh of size $n \times n$ was running in O(log n ) time. It was open for more than 8 years to obtain a faster algorithm for this important problem. Our main contribution is to provide the first breakthrough: we propose a deterministic list-ranking algorithm that runs in O(log* n ) time as well as a randomized one running in O(1) expected time, both on a reconfigurable mesh of size $n \times n$ . Our results open the door to a large number of efficient list-ranking-based algorithms on reconfigurable meshes.

We present an algorithm which computes the convex hull of a set of n spheres in dimension d in time O (n ⌜ d 2 ⌝ + n log n) . It is worst-case optimal in three dimensions and in even dimensions. The same method can also be used to compute the convex hull of a set of n homothetic convex objects of Ed. If the complexity of each object is constant, the time needed in the worst case is O (n ⌜ d 2 ri + n log n) .

In this paper, we propose an algorithm to compute the Delaunay triangulation of a set [Formula: see text] of n points in 3-dimensional space when the points lie in 2 planes. The algorithm is output-sensitive and optimal with respect to the input and the output sizes. Its time complexity is O(n log n+t), where t is the size of the output, and the extra storage is O(n).

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in R d , the maximum complexity of its Voronoi diagram under the L ∞ metric, and also under a simplicial distance function, are both shown to be $\Theta(n^{\lceil d/2 \rceil})$ . The upper bound for the case of the L ∞ metric follows from a new upper bound, also proved in this paper, on the maximum complexity of the union of n axis-parallel hypercubes in R d . This complexity is $\Theta(n^{\left\lceil d/2 \right\rceil})$ , for d ≥ 1 , and it improves to $\Theta(n^{\left\lfloor d/2 \right\rfloor})$ , for d ≥ 2 , if all the hypercubes have the same size. Under the L 1 metric, the maximum complexity of the Voronoi diagram of a set of n points in general position in R 3 is shown to be $\Theta(n^2)$ . We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations. (This increase does not occur with an appropriate modification of the diagram definition.) Finally, on-line algorithms are proposed for computing the Voronoi diagram of n points in R d under a simplicial or L ∞ distance function. Their expected randomized complexities are $O(n \log n + n ^{\left\lceil d/2 \right\rceil})$ for simplicial diagrams and $O(n ^{\left\lceil d/2 \right\rceil} \log ^{d-1} n)$ for L ∞ -diagrams.

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which classes of simple objects are {\em universal}, i.e. powerful enough to represent all graphs. In particular, we show that there is no constant $k$ for which the class of all polygons having $k$ or fewer sides is universal. However, we show by construction that every graph on $n$ vertices can be represented by polygons each having at most $2n$ sides. The construction can be carried out by an $O(n^2)$ algorithm. We also study the universality of classes of simple objects (translates of a single, not necessarily polygonal object) relative to cliques $K_n$ and similarly relative to complete bipartite graphs $K_{n,m}$.

Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i \in \R^2$ is his velocity. The problem we address is how to preprocess the postmen data so as to be able to efficiently answer two types of nearest neighbor queries. The first one asks ``who is the nearest postman at time $t_q$ to a dog located at point $s_q$?''. In the second type a query dog is located a point $s_q$ at time $t_q$, its velocity is $v_q>|v_i|$ (for all $i=1, \ldots , n$), and we want to know which postman the dog can catch first. We present two solutions to these problems, with tradeoff between preprocessing time and query time. Both solutions use deterministic data structures.

We build on the work of Dehne and Rau-Chaplin and give improved bounds for the multisearch problem on a hypercube. This is a parallel search problem where the elements in the structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q'. This problem is fundamental in computational geometry, for example it models planar point location in a slab. More precisely, we are given on a n-processor hypercube a sorted n-element sequence S and a set Q of n queries and we need to find for each query q [??]Q its location in the sorted S. Note that one cannot solve this problem by sorting S[??] Q, because every comparison- based parallel sorting algorithm needs to compare a pair q, q' [??]Q in constant time. We present an improved algorithm for the multisearch problem, one that takes 0(log n(log log n)3) time on a n-processor hypercube. This essentially replaces a logarithmic factor in the time complexities of previous schemes by a (log log n)3 factor. The hypercube model for which we claim our bounds is the standard one, with 0(1) memory registers per processor, and with one-port communication. Each register can store 0(log n) bits, so that a processor knows its ID.

International audience; The existing O(n log n) algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental algorithms for these problems is that the introduction of a new circle or parabola can cause Theta(n) structural changes, leading to Theta(n^2) total structural changes during the running of the algorithm. In this note we examine the geometry of these problems and show that, if the circles or parabolas are first sorted by appropriate parameters before constructing the convex hull or lower envelope incrementally, then each new addition may cause at most 3 changes in an amortized sense. These observations are then used to develop O(n log n) incremental algorithms for these problems.

This paper presents a general framework for the design and randomized analysis of geometric algorithms. These algorithms are on-line and the framework provides general bounds for their expected space and time complexities when averaging over all permutations of the input data. The method is general and can be applied to various geometric problems. The power of the technique is illustrated by new efficient on-line algorithms for constructing convex hulls and Voronoi diagrams in any dimension, Voronoi diagrams of line segments in the plane, arrangements of curves in the plane, and others.

The Delaunay Tree is a hierarchical data structure that has been introduced in [6] and analyzed in [7, 4]. For a given set of sites L in the plane and an order of insertion for these sites, the Delaunay Tree stores all the successive Delaunay triangulations. As proved before, the Delaunay Tree allows the insertion of a site in logarithmic expected time and linear expected space, when the insertion sequence is randomized.In this paper, we describe an algorithm maintaining the Delaunay Tree under insertions and deletions of sites. This can be done in O(log n) expected time for an insertion and O(log log n) expected time for a deletion, where n is the number of sites currently present in the structure. For deletions, by expected time, we mean averaging over all already inserted sites for the choice of the deleted sites. These results are optimal. The algorithm has been effectively coded and experimental results are given.

International audience

International audience; We describe in this paper an algorithm which dynamically maintains the trapezoidal map of an arrangement of line segments. This algorithm is a generalization of the Influence Graph data structure used by Boissonnat et al. to deal with the semi-dynamic case. Our complexity results are randomized, i.e. the insertion sequences are supposed to be evenly distributed among the n! possible sequences of $ segments, and when an object is deleted, we suppose that it can be any of the already inserted objects with the same probability. Under these assumptions the algorithm needs O(n+a) expected space, O(log n + a/n) expected insertion time, O( (1+ a/n)loglog n) expected deletion time and O(log n) time to locate any query point in the arrangement, where a is the current size of the arrangement and n the current number of segments.

International audience; Given is a set \s\ of $n$ points, each colored with one of $k \geq 3$ colours. We say that a triangle defined by three points of \s\ is 3-colored if its vertices have distinct colours. We prove in this paper that the problem of constructing the boundary of the union \ts\ of all such 3-colored triangles can be done in optimal $O(n \log n)$ time.

Special issue SoCG00; International audience; This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library CGAL.

International audience; Geometric algorithms are based on geometric objects such as points, lines and circles. The term kernel refers to a collection of representations for constant-size geometric objects and operations on these representations. This paper describes how such a geometry kernel can be designed and implemented in C++, having special emphasis on adaptability, extensibility and efficiency. We achieve these goals following the generic programming paradigm and using templates as our tools. These ideas are realized and tested in CGAL, the Computational Geometry Algorithms Library, see http://www.cgal.org/.

We present a new approach to the stereo-matching problem. Images are individually described by aneighborhood graph of line segments coming from a polygonal approximation of the contours. The matching process is defined as the exploration of the largest components of adisparity graph built from the descriptions of the two images, and is performed by an efficient prediction and propagation technique. This approach was tested on a variety of man-made environments, and it appears to be fast and robust enough for mobile robot navigation and three-dimensional part-positioning applications.

Computing the Delaunay triangulation of $n$ points requires usually a minimum of $\Omega(n\log n)$ operations, but in some special cases where some additional knowledge is provided, faster algorithms can be designed. Given two sets of points, we prove that, if the Delaunay triangulation of all the points is known, the Delaunay triangulation of each set can be computed in randomized expected linear time.

We introduce a new type of randomized incremental algorithms. Contrary to standard randomized incremental algorithms, theselazy randomized incremental algorithms are suited for computing structures that have a "nonlocal" definition. In order to analyze these algorithms we generalize some results on random sampling to such situations. We apply our techniques to obtain efficient algorithms for the computation of single cells in arrangements of segments in the plane, single cells in arrangements of triangles in space, and zones in arrangements of hyperplanes.

International audience; This paper presents how the space of spheres and shelling may be used to delete a point from a $d$-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex, the complexity is O(k log k), but we notice that this number only applies to low cost operations, while time consuming computations are only done a linear number of times. This algorithm may be viewed as a variation of Heller's algorithm [Heller, Symp. Spatial Data Handling 1990] which is popular in the geographic information system community. Unfortunately, Heller algorithm is false, as explained in this paper.

International audience; In this talk we describe some problems arising in practical implementation of algorithms from computational geometry. Going to robust algorithms needs to solve issues such as rounding errors and degeneracies. Most of the problems are closely related to the incompatibility between on one side algorithms designed for continuous data and on the other side the discrete nature of the data and the computations in an actual computer.

We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m vertices, containing an obstacle in a form of a simple polygon with $n$ vertices. We present an O(m+n) time algorithm finding the path, going around the obstacle, whose curvature is the smallest possible., 11 pages, 5 figures, abstract presented at European Symposium on Algorithms 1993

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, and small memory occupation. The location structure is organized into several levels. The lowest level just consists of the triangulation, then each level contains the triangulation of a small sample of the levels below. Point location is done by marching in a triangulation to determine the nearest neighbor of the query at that level, then the march restarts from that neighbor at the level below. Using a small sample (3%) allows a small memory occupation; the march and the use of the nearest neighbor to change levels quickly locate the query., Comment: 19 pages, 7 figures Proc. 14th Annu. ACM Sympos. Comput. Geom., 106--115, 1998