Algorithmic paradigms: examples in computational geometry

ABSTRACT

We present a collection of algorithms that solve problems from the realm of computational geometry to illustrate several basic notions in algorithm design and analysis. Computational geometry is a young discipline that has much to offer both as a field of research and as a source of instruction materials. This paper aims to serve a dual purpose by (a) outlining results that might prick the interest of researchers looking for greener pastures (so to speak) for investigation; and (b) showing the pedagogic value of these results for teachers of algorithm design and analysis.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Computer science education

General Terms:
Algorithms, Human Factors, Theory