On a circle-cover minimization problem

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

*Corresponding author for this work

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

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
Volume18
Issue number2
DOIs
StatePublished - Feb 28 1984

Keywords

  • Analysis of algorithms
  • computational geometry
  • minimum cover

ASJC Scopus subject areas

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

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

Cite this