Courbes et Surfaces Médiatrices, et Diagramme de Voronoï d’une famille finie de demi-droites parallèles dans R3

Abstract

Cette thèse est composée de trois parties principales : les calculs des courbes médiatrices de deux courbes ou d’un point et d’une courbe dans le plan, des surfaces médiatrices de deux surfaces dans R3, et du diagramme de Voronoï d’une famille finie de demi-droites parallèles de même orientation. Ces trois sujets sont étroitement liés et trouvent des applications dans le domaine de la CAO/CGAO et de la géométrie algorithmique. Dans ces trois sujets, nous allons présenter des méthodes algorithmiques pour obtenir une certaine représentation de l’objet qui nous intéresse : la courbe médiatrice, la surface médiatrice ou le diagramme de Voronoï. En utilisant la règle de Cramer généralisée et certaines méthodes d’élimination algébrique, nous présentons une nouvelle approche pour déterminer une paramétrisation algébrique exacte (rationnelle ou non rationnelle) de la courbe médiatrice de deux courbes planes rationnelles. L’approche est, ensuite, généralisée pour déterminer une paramétrisation algébrique exacte (rationnelle ou non rationnelle) de la surface médiatrice de deux surfaces rationnelles de petit degré. La méthode est appliquée pour obtenir les paramétrisations de la médiatrice de deux courbes planes rationnelles, dans lesquelles une des courbes est un cercle ou une droite. D’autre part, nous montrons, aussi, comment il est facile d’obtenir les paramétrisations de la médiatrice de paires de surfaces suivantes : plan-quadrique, plan-tore, cylindre circulaire-quadrique non développable, cylindre circulaire-tore, cylindre cylindre, cylindre-cône et cône-cône. Les paramétrisations obtenues sont rationnelles dans la plupart des cas. Dans le reste des cas, les paramétrisations contiennent des racines carrées qui est bien adapté pour déterminer une bonne approximation de la médiatrice. Nous présentons aussi une approche différente traitant du problème de la courbe médiatrice plane. Cette nouvelle méthode utilise la couleur dynamique en GeoGebra pour les caractérisations géométrique et numérique de la courbe médiatrice de deux objets géométriques dans le plan (deux courbes, ou une courbe et un point). Même si elle ne fournit pas de représentation algébrique, la méthode peut conduire au calcul d’une représentation approximative de la courbe médiatrice. Le diagramme de Voronoï (VD) est une structure de données fondamentale de la géométrie algorithmique avec des applications très variées dans des domaines théoriques et pratiques. Nous considérons le VD d’un ensemble fini de demi-droites parallèles de même orientation restreint à un domaine compact D0 ⊂ R3 pour la distance euclidienne. Ce nouveau type de VD peut être utilisé pour apporter des réponses efficaces à certains problèmes dans l’industrie de forage, tels que l’hydraulique ou la mine. Nous présentons un algorithme approximatif efficace pour le calcul de ce VD, en utilisant le processus de subdivision produisant un maillage qui représente la topologie de VD dans D0