Un nombre croissant d'applications n'ecessite d'opérer des traitements algorithmiques sur des objets tridimensionnels. Le plus souvent, ceux-ci sont représentés par des surfaces triangulées. Cette thèse aborde trois problèmes posés par la manipulation de ces surfaces. On donne d'abord un algorithme qui, étant donnée une surface triangulée, construit une triangulation de Delaunay volumique la contenant comme sous-complexe. De telles triangulations sont utiles par exemple pour le calcul scientifique. Puis, on donne une généralisation de la courbure s'appliquant à des surfaces non nécessairement lisses, donc en particulier aux surfaces triangulées, et on étudie sa stabilité. Celle-ci est ensuite utilisée dans un algorithme de remaillage de surfaces triangulées visant à optimiser le rapport complexité/distortion. Enfin, on donne un algorithme de maillage de surfaces implicites garantissant que l'approximation produite a la même topologie que la surface initiale.

Ad-Hoc Wireless routing has become an important area of research in the last few years due to the massive increase in wireless devices. Computational Geometry is relevant in attempts to build stable, low power routing schemes. It is only recently, however, that models have been expanded to consider devices with a non-uniform broadcast range, and few properties are known. In particular, we find, via both theoretical and experimental methods, extremal properties for the Localized Delaunay Triangulation over the Mutual Inclusion Graph. We also provide a distributed, sub-quadratic algorithm for the generation of the structure.

Soit S un ensemble de points pris sur une surface F d'équation z = f(x,y) ; on projette S dans le plan (xOy), et on désire construire une triangulation de l'enveloppe convexe de la projection de S qui déterminera une approximation linéaire par morceaux de F, dont la qualité sera liée à une mesure de l'erreur d'approximation de la surface. Il a été récemment prouvé que la triangulation de Delaunay était optimale pour des critères de normes Lp, lorsqu'il s'agissait d'approcher linéairement toute fonction quadratique convexe, dans un espace de dimension quelconque. En revanche, très peu de recherches ont été menées lorsque la surface n'est pas convexe. Ce mémoire propose donc d'étudier l'approximation par une tri- angulation, pour des critères de normes L1 et L2, d'une surface non convexe d'équation la plus simple possible : le paraboloïde hyperbolique défini par z = x2 − y2. Une construction est ainsi donnée pour déterminer, de manière naturelle, les courbes de séparation d'un triangle ∆, c'est-à-dire les limites du plan pour lesquelles ∆ doit être conservé dans une triangulation localement op- timale du paraboloïde hyperbolique. Des algorithmes de triangulation qui font appel à diverses heuristiques fondées sur les courbes de séparation ont été abon- damment testés ; une amélioration significative par rapport à la triangulation de Delaunay a été mise en évidence. Une comparaison avec des triangulations glob- alement optimales, dont l'obtention n'est possible qu'au moyen de programmes de complexité exponentielle, prouve que ces algorithmes rendent finalement de "bonnes" triangulations. Les recherches montrent qu'un tel procédé peut facile- ment être généralisé à toutes les surfaces définies par des fonctions quadratiques, de la forme z = αx2 + βy2 + γxy + δ1x + δ2y + δ3.

The online and data stream models of computation have recently attracted considerable research attention due to many real-world applications in various areas such as data mining, machine learning, distributed computing, and robotics. In both these models, input items arrive one at a time, and the algorithms must decide based on the partial data received so far, without any secure information about the data that will arrive in the future. In this thesis, we investigate efficient algorithms for a number of fundamental geometric optimization problems in the online and data stream models. The problems studied in this thesis can be divided into two major categories: geometric clustering and computing various extent measures of a set of points. In the online setting, we show that the basic unit clustering problem admits non-trivial algorithms even in the simplest one-dimensional case: we show that the naive upper bounds on the competitive ratio of algorithms for this problem can be beaten using randomization. In the data stream model, we propose a new streaming algorithm for maintaining "core-sets" of a set of points in fixed dimensions, and also, introduce a new simple framework for transforming a class of offline algorithms to their equivalents in the data stream model. These results together lead to improved streaming approximation algorithms for a wide variety of geometric optimization problems in fixed dimensions, including diameter, width, k-center, smallest enclosing ball, minimum-volume bounding box, minimum enclosing cylinder, minimum-width enclosing spherical shell/annulus, etc. In high-dimensional data streams, where the dimension is not a constant, we propose a simple streaming algorithm for the minimum enclosing ball (the 1-center) problem with an improved approximation factor.

Finding a shortest path is one of the most well-studied optimization problems. In this thesis we focus on shortest paths in geometric and graph theoretic settings subject to different feasibility constraints that arise in practical applications of such paths. One of the most fundamental problems in computational geometry is finding shortest paths in terrains, which has many applications in robotics, computer graphics and Geographic Information Systems (GISs). There are many variants of the problem in which the feasibility of a path is determined by some geometric property of the terrain. One such variant is the shortest descending path (SDP) problem, where the feasible paths are those that always go downhill. We need to compute an SDP, for example, for laying a canal of minimum length from the source of water at the top of a mountain to fields for irrigation purpose, and for skiing down a mountain along a shortest route. The complexity of finding SDPs is open. We give a full characterization of the bend angles of an SDP, showing that they follow a generalized form of Snell's law of refraction of light. We also reduce the SDP problem to the problem of finding an SDP through a given sequence of faces, by adapting the sequence tree approach of Chen and Han for our problem. Our results have two implications. First, we isolate the difficult aspect of SDPs. The difficulty is not in deciding which face sequence to use, but in finding the SDP through a given face sequence. Secondly, our results help us identify some classes of terrains for which the SDP problem is solvable in polynomial time. We give algorithms for two such classes. The difficulty of finding an exact SDP motivates the study of approximation algorithms for the problem. We devise two approximation algorithms for SDPs in general terrains---these are the first two algorithms to handle the SDP problem in such terrains. The algorithms are robust and easy-to-implement. We also give two approximation algorithms for the case when a face sequence is given. The first one solves the problem by formulating it as a convex optimization problem. The second one uses binary search together with our characterization of the bend angles of an SDP to locate an approximate path. We introduce a generalization of the SDP problem, called the shortest gently descending path (SGDP) problem, where a path descends but not too steeply. The additional constraint to disallow a very steep descent makes the paths more realistic in practice. For example, a vehicle cannot follow a too steep descent---this is why a mountain road has hairpin bends. We give two easy-to-implement approximation algorithms for SGDPs, both using the Steiner point approach. Between a pair of points there can be many SGDPs with different number of bends. In practice an SGDP with fewer bends or smaller total turn-angle is preferred. We show using a reduction from 3-SAT that finding an SGDP with a limited number of bends or a limited total turn-angle is hard. The hardness result applies to a generalization of the SGDP problem called the shortest anisotropic path problem, which is a well-studied computational geometry problem with many practical applications (e.g., robot motion planning), yet of unknown complexity. Besides geometric shortest paths, we also study a variant of the shortest path problem in graphs: given a weighted graph G and vertices s and t, and given a set X of forbidden paths in G, find a shortest s-t path P such that no path in X is a subpath of P. Path P is allowed to repeat vertices and edges. We call each path in X an exception, and our desired path a shortest exception avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception x in X only when a path containing x fails. This situation arises in computing shortest paths in optical networks. We give an easy-to-implement algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The algorithm handles a forbidden path using vertex replication, i.e., replicating vertices and judiciously deleting edges so as to remove the forbidden path but keep all of its subpaths. The main challenge is that vertex replication can result in an exponential number of copies of any forbidden path that overlaps the current one. The algorithm couples vertex replication with the "growth" of a shortest path tree in such a way that the extra copies of forbidden paths produced during vertex replication are immaterial.

The main topic of this thesis is the development of computational search methods that are useful in drug design applications. The emphasis is on exhaustiveness of the search method such that it can guarantee a certain level of geometric accuracy. In particular, the following two problems are addressed: (i) Prediction of binding mode of a drug molecule to a receptor and (ii) prediction of crystal structures of drug molecules. Predicting the binding mode(s) of a drug molecule to a target receptor is pivotal in structure-based rational drug design. In contrast to most approaches to solve this problem, the idea in this work is to analyze the search problem from a computational perspective. By building on top of an existing docking tool, new methods are proposed and relevant computational results are proven. These methods and results are applicable for other place-and-join frameworks as well. A fast approximation scheme for the docking of rigid fragments is described that guarantees certain geometric approximation factors. It is also demonstrated that this can be translated into an energy approximation for simple scoring functions. A polynomial time algorithm is developed for the matching phase of the docked rigid fragments. It is demonstrated that the generic matching problem is NP-hard. At the same time the optimality of the proposed algorithm is proven under certain scoring function conditions. The matching results are also applicable for some of the fragment-based de novo design methods. On the practical side, the proposed method is tested on 829 complexes from the PDB. The results show that the closest predicted pose to the native structure has the average RMS deviation of 1.06 °A. The prediction of crystal structures of small organic molecules has significantly improved over the last two decades. Most of the new developments, since the first blind test held in 1999, have occurred in the lattice energy estimation subproblem. In this work, a new efficient systematic search method that avoids random moves is proposed. It systematically searches through the space of possible crystal structures and conducts search space cuts based on statistics collected from the structural databases. It is demonstrated that the fast search method for rigid molecules can be extended to include flexible molecules as well. Also, the results of some prediction experiments are provided showing that in most cases the systematic search generates a structure with less than 1.0°A RMSD from the experimental crystal structure. The scoring function that has been developed for these experiments is described briefly. It is also demonstrated that with a more accurate lattice energy estimation function, better results can be achieved with the proposed robust search method.

The online and data stream models of computation have recently attracted considerable research attention due to many real-world applications in various areas such as data mining, machine learning, distributed computing, and robotics. In both these models, input items arrive one at a time, and the algorithms must decide based on the partial data received so far, without any secure information about the data that will arrive in the future. In this thesis, we investigate efficient algorithms for a number of fundamental geometric optimization problems in the online and data stream models. The problems studied in this thesis can be divided into two major categories: geometric clustering and computing various extent measures of a set of points. In the online setting, we show that the basic unit clustering problem admits non-trivial algorithms even in the simplest one-dimensional case: we show that the naive upper bounds on the competitive ratio of algorithms for this problem can be beaten using randomization. In the data stream model, we propose a new streaming algorithm for maintaining "core-sets" of a set of points in fixed dimensions, and also, introduce a new simple framework for transforming a class of offline algorithms to their equivalents in the data stream model. These results together lead to improved streaming approximation algorithms for a wide variety of geometric optimization problems in fixed dimensions, including diameter, width, k-center, smallest enclosing ball, minimum-volume bounding box, minimum enclosing cylinder, minimum-width enclosing spherical shell/annulus, etc. In high-dimensional data streams, where the dimension is not a constant, we propose a simple streaming algorithm for the minimum enclosing ball (the 1-center) problem with an improved approximation factor.

Finding a shortest path is one of the most well-studied optimization problems. In this thesis we focus on shortest paths in geometric and graph theoretic settings subject to different feasibility constraints that arise in practical applications of such paths. One of the most fundamental problems in computational geometry is finding shortest paths in terrains, which has many applications in robotics, computer graphics and Geographic Information Systems (GISs). There are many variants of the problem in which the feasibility of a path is determined by some geometric property of the terrain. One such variant is the shortest descending path (SDP) problem, where the feasible paths are those that always go downhill. We need to compute an SDP, for example, for laying a canal of minimum length from the source of water at the top of a mountain to fields for irrigation purpose, and for skiing down a mountain along a shortest route. The complexity of finding SDPs is open. We give a full characterization of the bend angles of an SDP, showing that they follow a generalized form of Snell's law of refraction of light. We also reduce the SDP problem to the problem of finding an SDP through a given sequence of faces, by adapting the sequence tree approach of Chen and Han for our problem. Our results have two implications. First, we isolate the difficult aspect of SDPs. The difficulty is not in deciding which face sequence to use, but in finding the SDP through a given face sequence. Secondly, our results help us identify some classes of terrains for which the SDP problem is solvable in polynomial time. We give algorithms for two such classes. The difficulty of finding an exact SDP motivates the study of approximation algorithms for the problem. We devise two approximation algorithms for SDPs in general terrains---these are the first two algorithms to handle the SDP problem in such terrains. The algorithms are robust and easy-to-implement. We also give two approximation algorithms for the case when a face sequence is given. The first one solves the problem by formulating it as a convex optimization problem. The second one uses binary search together with our characterization of the bend angles of an SDP to locate an approximate path. We introduce a generalization of the SDP problem, called the shortest gently descending path (SGDP) problem, where a path descends but not too steeply. The additional constraint to disallow a very steep descent makes the paths more realistic in practice. For example, a vehicle cannot follow a too steep descent---this is why a mountain road has hairpin bends. We give two easy-to-implement approximation algorithms for SGDPs, both using the Steiner point approach. Between a pair of points there can be many SGDPs with different number of bends. In practice an SGDP with fewer bends or smaller total turn-angle is preferred. We show using a reduction from 3-SAT that finding an SGDP with a limited number of bends or a limited total turn-angle is hard. The hardness result applies to a generalization of the SGDP problem called the shortest anisotropic path problem, which is a well-studied computational geometry problem with many practical applications (e.g., robot motion planning), yet of unknown complexity. Besides geometric shortest paths, we also study a variant of the shortest path problem in graphs: given a weighted graph G and vertices s and t, and given a set X of forbidden paths in G, find a shortest s-t path P such that no path in X is a subpath of P. Path P is allowed to repeat vertices and edges. We call each path in X an exception, and our desired path a shortest exception avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception x in X only when a path containing x fails. This situation arises in computing shortest paths in optical networks. We give an easy-to-implement algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The algorithm handles a forbidden path using vertex replication, i.e., replicating vertices and judiciously deleting edges so as to remove the forbidden path but keep all of its subpaths. The main challenge is that vertex replication can result in an exponential number of copies of any forbidden path that overlaps the current one. The algorithm couples vertex replication with the "growth" of a shortest path tree in such a way that the extra copies of forbidden paths produced during vertex replication are immaterial.

The main topic of this thesis is the development of computational search methods that are useful in drug design applications. The emphasis is on exhaustiveness of the search method such that it can guarantee a certain level of geometric accuracy. In particular, the following two problems are addressed: (i) Prediction of binding mode of a drug molecule to a receptor and (ii) prediction of crystal structures of drug molecules. Predicting the binding mode(s) of a drug molecule to a target receptor is pivotal in structure-based rational drug design. In contrast to most approaches to solve this problem, the idea in this work is to analyze the search problem from a computational perspective. By building on top of an existing docking tool, new methods are proposed and relevant computational results are proven. These methods and results are applicable for other place-and-join frameworks as well. A fast approximation scheme for the docking of rigid fragments is described that guarantees certain geometric approximation factors. It is also demonstrated that this can be translated into an energy approximation for simple scoring functions. A polynomial time algorithm is developed for the matching phase of the docked rigid fragments. It is demonstrated that the generic matching problem is NP-hard. At the same time the optimality of the proposed algorithm is proven under certain scoring function conditions. The matching results are also applicable for some of the fragment-based de novo design methods. On the practical side, the proposed method is tested on 829 complexes from the PDB. The results show that the closest predicted pose to the native structure has the average RMS deviation of 1.06 °A. The prediction of crystal structures of small organic molecules has significantly improved over the last two decades. Most of the new developments, since the first blind test held in 1999, have occurred in the lattice energy estimation subproblem. In this work, a new efficient systematic search method that avoids random moves is proposed. It systematically searches through the space of possible crystal structures and conducts search space cuts based on statistics collected from the structural databases. It is demonstrated that the fast search method for rigid molecules can be extended to include flexible molecules as well. Also, the results of some prediction experiments are provided showing that in most cases the systematic search generates a structure with less than 1.0°A RMSD from the experimental crystal structure. The scoring function that has been developed for these experiments is described briefly. It is also demonstrated that with a more accurate lattice energy estimation function, better results can be achieved with the proposed robust search method.

Ad-Hoc Wireless routing has become an important area of research in the last few years due to the massive increase in wireless devices. Computational Geometry is relevant in attempts to build stable, low power routing schemes. It is only recently, however, that models have been expanded to consider devices with a non-uniform broadcast range, and few properties are known. In particular, we find, via both theoretical and experimental methods, extremal properties for the Localized Delaunay Triangulation over the Mutual Inclusion Graph. We also provide a distributed, sub-quadratic algorithm for the generation of the structure.