On a circle-cover minimization problem

C. C. Lee*, D. T. Lee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


Given a set of n circular-arcs A1, A2,...,An, we consider the problem of finding a minimum number of circular-arcs whose union covers the circle. Specifically, if the endpoints of these n arcs are given, we show that O(n log n) is both sufficient and necessary for solving the minimum cover problem. Furthermore, with O(n log n) preprocessing time we find the minimum cover in O(n) time.

Original languageEnglish (US)
Pages (from-to)109-115
Number of pages7
JournalInformation Processing Letters
Issue number2
StatePublished - Feb 28 1984


  • Analysis of algorithms
  • computational geometry
  • minimum cover

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'On a circle-cover minimization problem'. Together they form a unique fingerprint.

Cite this