The Interface Between Computational and Combinatorial Geometry
Micha Sharir, Tel Aviv University, Israel

Computational geometry studies the design of efficient algorithms for computing with geometric data. It provides an interface between (i) the numerous application areas (bioinformatics, robotics, graphics, to mention a few), (ii) the theory of graph algorithms and data structures, and (iii) various branches in mathematics, such as topology, algebraic geometry and combinatorial geometry. I will highlight several manifestations of the interface between the computational aspects of the area and the mathematical techniques that it uses (and often develops), including (a) examples, where sharp bounds on the complexity of the output can be used to enhance the efficiency of geometric algorithms, and (b) illustrations of techniques for the design of efficient geometric algorithms that are "almost identical" to techniques for solving rather unrelated problems in combinatorial geometry.