The power of geometric duality

Bernard Chazelle, Leo J. Guibas, D. T. Lee

Research output: Contribution to journalArticle

157 Scopus citations

Abstract

This paper uses a new formulation of the notion of duality that allows the unified treatment of a number of geometric problems. In particular, we are able to apply our approach to solve two long-standing problems of computational geometry: one is to obtain a quadratic algorithm for computing the minimum-area triangle with vertices chosen among n points in the plane; the other is to produce an optimal algorithm for the half-plane range query problem. This problem is to preprocess n points in the plane, so that given a test half-plane, one can efficiently determine all points lying in the half-plane. We describe an optimal O(k + log n) time algorithm for answering such queries, where k is the number of points to be reported. The algorithm requires O(n) space and O(n log n) preprocessing time. Both of these results represent significant improvements over the best methods previously known. In addition, we give a number of new combinatorial results related to the computation of line arrangements.

Original languageEnglish (US)
Pages (from-to)76-90
Number of pages15
JournalBIT
Volume25
Issue number1
DOIs
StatePublished - Mar 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The power of geometric duality'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., Guibas, L. J., & Lee, D. T. (1985). The power of geometric duality. BIT, 25(1), 76-90. https://doi.org/10.1007/BF01934990