On a circle-cover minimization problem

C. C. Lee; D. T. Lee

doi:10.1016/0020-0190(84)90033-4

On a circle-cover minimization problem

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

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

32 Scopus citations

Abstract

Given a set of n circular-arcs A₁, A₂,...,A_n, 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 language	English (US)
Pages (from-to)	109-115
Number of pages	7
Journal	Information Processing Letters
Volume	18
Issue number	2
DOIs	https://doi.org/10.1016/0020-0190(84)90033-4
State	Published - 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

Access to Document

10.1016/0020-0190(84)90033-4

Cite this

@article{dd907d476ddd41078c41191a6d5120f2,

title = "On a circle-cover minimization problem",

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.",

keywords = "Analysis of algorithms, computational geometry, minimum cover",

author = "Lee, {C. C.} and Lee, {D. T.}",

note = "Funding Information: * Thk research was supported in part by the National Science Foundation under Grants MCS 8202359 and ECS 8121741.",

year = "1984",

month = feb,

day = "28",

doi = "10.1016/0020-0190(84)90033-4",

language = "English (US)",

volume = "18",

pages = "109--115",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - On a circle-cover minimization problem

AU - Lee, C. C.

AU - Lee, D. T.

N1 - Funding Information: * Thk research was supported in part by the National Science Foundation under Grants MCS 8202359 and ECS 8121741.

PY - 1984/2/28

Y1 - 1984/2/28

N2 - 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.

AB - 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.

KW - Analysis of algorithms

KW - computational geometry

KW - minimum cover

UR - http://www.scopus.com/inward/record.url?scp=0021374353&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021374353&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(84)90033-4

DO - 10.1016/0020-0190(84)90033-4

M3 - Article

AN - SCOPUS:0021374353

SN - 0020-0190

VL - 18

SP - 109

EP - 115

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

On a circle-cover minimization problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this