Circles through two points that always enclose many points


Journal Article

This paper proves that any set of n points in the plane contains two points such that any circle through those two points encloses at least {Mathematical expression} points of the set. The main ingredients used in the proof of this result are edge counting formulas for k-order Voronoi diagrams and a lower bound on the minimum number of semispaces of size at most k. © 1989 Kluwer Academic Publishers.

Full Text

Cited Authors

  • Edelsbrunner, H; Hasan, N; Seidel, R; Shen, XJ

Published Date

  • October 1, 1989

Published In

Volume / Issue

  • 32 / 1

Start / End Page

  • 1 - 12

Electronic International Standard Serial Number (EISSN)

  • 1572-9168

International Standard Serial Number (ISSN)

  • 0046-5755

Digital Object Identifier (DOI)

  • 10.1007/BF00181432

Citation Source

  • Scopus