Titre / Title: Sur l'algorithme de Fortune
Résumé / Abstract:
L'algorithme de balayage de Fortune est connu comme l'algorithme le plus efficace pour construire le diagramme de Voronoï d'un ensemble fini S de points du plan. Nous proposons ici différentes améliorations : nous construisons le diagramme de Delaunay et non une triangulation, nous traitons tous les cas particuliers des points cocycliques ou alignés, nous utilisons les cartes comme structures de données et nous réduisons le nombre d'événements. Le temps d'exécution de l'algorithme est ainsi divisé par 2.
Version : Française
Titre / Title: Construction de l'enveloppe convexe dans le plan par balayage selon un retangle
Résumé / Abstract:
Nous introduisons une nouvelle méthode de balayage qui
consiste à balayer le plan par un rectangle et nous utilisons cette
technique pour construire l'enveloppe convexe d'un ensemble de points du
plan.
Nous obtenons ainsi un algorithme dont les performances pratiques sont
comparables à celles des algorithmes les plus efficaces.
Version : Française
Titre / Title: An increasing-circle sweep-algorithm to construct the Delaunay diagram in the plane
Résumé / Abstract:
We present a new way to compute the Delaunay diagram of a planar set S of n sites in O(n log n) time by using a plane sweep technique. We sweep the plane by a circle whose center is a fixed point in the convex hull of S and whose radius increases from 0 to infinity. This method is interesting notably when the diagram has to be constructed locally around a given point. We do not know of any method to reduce the sweep circle algorithm to a sweep line algorithm.
Version : Anglaise 
Titre / Title: Linear expected sweep-algorithm for planar convex hulls
Résumé / Abstract:
--- Soon ---
Avant novembre 1999
Titre / Title: Construction du diagramme de Delaunay des points les plus éloignés par balayage selon un rayon décroissant
Résumé / Abstract:
Nous présentons un algorithme qui construit le diagramme de
Delaunay des points les plus éloignés Del-1(S)
d'un ensemble S de points du plan en balayant le plan selon un rayon
décroissant.
Au fur et à mesure du balayage, des sommets, des côtés
et des faces s'ajoutent à un diagramme courant qui formera Del-1(S)
quand S sera intérieur à l'enveloppe convexe de S.
Une première version calcule Del-1(S) pour un ensemble
quelconque de sites en O(n log n).
Une deuxième version en générale plus rapide calcule d'abord
l'enveloppe convexe de S en O(n' log h) où n' est
le nombre de sites balayés par l'algorithme et h le nombre de sites
extrémaux de conv(S).
Puis cette seconde version calcule Del-1(T) pour l'ensemble
T des sites extrémaux de S trouvés en
O(h log h).
Version : Française
Le chapitre de ma thèse ou quelquechose s'en apporchant (avant la soutenance en Novembre ou juste après).
La version HTML générée par Word n'est pas en vrai HTML !
Je suis obligé de faire une bonne partie à la main.
Le texte intégral de la thèse sera diponible en novembre 1999, juste après la soutenance.
Titre / Title: A shrinking-circle sweep-algorithm to construct the furthest site Delaunay diagram in the plane
Résumé / Abstract:
We present a new way to compute the furthest site Delaunay diagram of a planar set S of n sites in O(n log n) time by using a sweep technique. We sweep the plane by a circle whose center is a fixed point in the convex hull of S and whose radius decreases from infinity to 0.
Version : Anglaise
Titre / Title: Sweeping along a polygonal line to construct a Delaunay diagram
Résumé / Abstract:
We present an algorithm that modifies a triangulation in order to get a Delaunay triangulation. It is based on the notion of a lob which can be found by sweeping along a polygonal line. Rather than doing an immediate reconstruction when deleting an illegal edge (i.e., not a Delaunay edge) as in the "diagonal flip", this algorithm deletes illegal edges and delays the reconstruction. This algorithm can replace to advantageously the diagonal flip. It is versatile and can also triangulate a convex hull, and can also be tuned to build a constrained Delaunay triangulation.
Version : Anglaise
--- Soon ---