Resumen de Curvas y superficies bisectrices y diagrama de Voronoi de una familia finita de semirrectas paralelas en R3

Ibrahim Adamou

• español

  Este trabajo consta de tres partes principales : el calculo de las bisectrices de dos curvas o de un punto y una curva en el plano, de la superficie bisectriz de dos superficies en R3, y del diagrama de Voronoi de una familia finita de semirrectas paralelas y con la misma orientación en R3. Estos temas están estrechamente relacionados y tienen aplicaciones en CAD/CAGD y en Geometría Computacional. Se presenta un nuevo método para determinar, utilizando la regla de Cramer generalizada y métodos de eliminación adecuados, una parametrización algebraica exacta (racional o no racional) de la curva bisectriz de dos curvas planas racionales dadas. Este método se generaliza para determinar una parametrización algebraica exacta de la superficie bisectriz de dos superficies racionales de grado bajo. El método se aplica, en particular, para obtener parametrizaciones de la bisectriz de dos curvas planas racionales, cuando una de ellas es una circunferencia o una recta. Por otro lado, se muestra cómo obtener fácilmente una parametrizacin de la bisectriz de los siguientes pares de superficies : plano y cuádrica, plano y toro, cilindro circular y cuádrica no desarrollable, cilindro circular y toro, dos cilindros, cilindro y cono, y dos conos. Estas parametrizaciones son racionales en la mayora de los casos. En los casos restantes, la parametrización contiene una raíz cuadrada, que resulta adecuada para determinar una buena aproximación de la bisectriz. Además, se presenta un enfoque diferente para el problema de la curva bisectriz plana. Este nuevo método utiliza color dinámico en GeoGebra para el cálculo de una caracterización geométrica y numérica de la bisectriz de dos objetos geométricos en el plano (dos curvas, o una curva y un punto). Aunque no proporciona una representación algebraica, el método permite el cálculo de una representación aproximada de la curva bisectriz. El diagrama de Voronoi (DV) es una estructura de datos fundamental en geometría computacional con diversas aplicaciones en distintas áreas teóricas y prácticas. Se estudia el DV de un conjunto de semirrectas paralelas y con la misma orientación, restringidas a un dominio compacto D0 ? R3, con respecto a la distancia euclidiana. Este nuevo tipo de DV se puede utilizar para proporcionar una solución eficiente a algunos problemas relacionados con la perforación, en industrias tales como la hidráulica o la minería. Se presenta un algoritmo eficiente para calcular una aproximación de un DV de esa clase, utilizando un proceso de subdivisión, que produce una malla que representa correctamente la topología del DV.

• English

  This thesis has three main parts: computation of the bisectors of two curves or a point and a curve in the plane, of the bisector of two surfaces in R3, and of the Voronoi diagram of a finite family of parallel half lines in R3, with the same orientation. These subjects are closely related, and have applications in CAD/CAGD and Computational Geometry. In each of the three parts, we present algorithmic methods for computing certain representations of the geometric object of interest: the bisector curve, the bisector surface, or the Voronoi diagram. We present a new approach to determine, using the generalized Cramer�s rule and suitable elimination steps, an exact algebraic parameterization (rational or non rational) of the bisector curve of two given planar rational curves. The approach is, then, generalized to determine an exact algebraic parameterization of the bisector surface of two low degree rational surfaces. In particular, we apply the method to obtain parametrizations of the bisector of two rational plane curves, when one of them is a circle or a straight line. On the other hand, we show how to easily obtain parametrizations of the bisector of the following pairs of surfaces: planequadric, plane-torus, circular cylinder-non developable quadric, circular cylindertorus, cylinder-cylinder, cylinder-cone and cone-cone. These parametrizations are rational in most cases. In the remaining cases the parametrization involves one square root which is well-suited to determine a good approximation of the bisector. In addition, a different approach for the bisector curve problem will be presented. This new method uses dynamic color in GeoGebra for the computation of a geometric and numerical characterization of the bisector of two planar geometric objects (two curves, or a curve and a point). Even if it does not provide an algebraic representation, the method could lead to the computation of an approximate representation of the bisector curve. The Voronoï diagram (VD) is a fundamental data structure in computational geometry with various applications in theoretical and practical areas. We consider the VD of a set of parallel half-lines, with the same orientation, constrained to a compact domain D0 ? R3, with respect to the Euclidean distance. This new kind of VD can be used to provide an efficient solution to some problems in the drilling industry, such as hydraulic or mining. We present an efficient approximate algorithm for computing such VD, using a box subdivision process, which produces a mesh representing the topology of the VD in D0.

• français

  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, 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ônecône. Les paramétrisations obtenues sont rationnelles dans la plupart des cas. Dans le reste des cas, les paramétrisations contiennent de racines carrées qui est bien adopté pour determiner une bonne approximation de la médiatrice. Nous présentons aussi une différente approche 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 tel VD, en utilisant le processus de subdivision produisant un maillage qui représente la topologie de VD dans D0.