Computing largest empty circles with location constraints

Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review


Let Q = {q1, q2,..., qn} be a set of n points on the plane. The largest empty circle (LEG) problem consists in finding the largest circle C with center in the convex hull of Q such that no point qi εQ lies in the interior of C. Shamos recently outlined an O(n log n) algorithm for solving this problem.(9) In this paper it is shown that this algorithm does not always work correctly. A different approach is proposed here and shown to also result in an O(n log n) algorithm. The new approach has the advantage that it can also solve more general problems. In particular, it is shown that if the center of C is constrained to lie in an arbitrary convex n-gon, an 0(n log n) algorithm can still be obtained. Finally, an 0(n log n +k log n) algorithm is given for solving this problem when the center of C is constrained to lie in an arbitrary simple n-gon P. where k denotes the number of intersections occurring between edges of P and edges of the Voronoi diagram of Q and k ≤O(n2).

Original languageEnglish (US)
Pages (from-to)347-358
Number of pages12
JournalInternational Journal of Computer & Information Sciences
Issue number5
StatePublished - Oct 1983


  • Largest empty circle
  • Voronoi diagram
  • algorithms
  • complexity
  • computational geometry
  • facility location
  • operations research
  • polygons

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'Computing largest empty circles with location constraints'. Together they form a unique fingerprint.

Cite this