Minimum blocking sets of circles for a set of lines in the plane

N. Jovanovic; J.H.M. Korst; A.J.E.M. Janssen

Minimum blocking sets of circles for a set of lines in the plane

N. Jovanovic, J.H.M. Korst, A.J.E.M. Janssen

Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

6 Citations (Scopus)

Abstract

A circle C is occluded by a set of circles C1; : : : ;Cn if every line that intersects C also intersects at least one of the Ci; i = 1; : : : ; n. In this paper, we focus on determining the minimum number of circles that occlude a given circle assuming that all circles have radius 1 and their mutual distance is at least d. As main contribution of this paper, we present upper and lower bounds on this minimal number of circles for 2 =d =4, as well as the algorithms we used to derive them.

Original language	English
Title of host publication	Proceedings 20th Canadian Conference on Computational Geometry (CCCG'08, Montréal, Québec, Canada, August 13-15, 2008)
Pages	91-94
Publication status	Published - 2008

Fingerprint Dive into the research topics of 'Minimum blocking sets of circles for a set of lines in the plane'. Together they form a unique fingerprint.

Cite this

@inproceedings{a1defeaaec5f4d45ab30e372929631d2,

title = "Minimum blocking sets of circles for a set of lines in the plane",

abstract = "A circle C is occluded by a set of circles C1; : : : ;Cn if every line that intersects C also intersects at least one of the Ci; i = 1; : : : ; n. In this paper, we focus on determining the minimum number of circles that occlude a given circle assuming that all circles have radius 1 and their mutual distance is at least d. As main contribution of this paper, we present upper and lower bounds on this minimal number of circles for 2 =d =4, as well as the algorithms we used to derive them.",

author = "N. Jovanovic and J.H.M. Korst and A.J.E.M. Janssen",

year = "2008",

language = "English",

pages = "91--94",

booktitle = "Proceedings 20th Canadian Conference on Computational Geometry (CCCG'08, Montr{\'e}al, Qu{\'e}bec, Canada, August 13-15, 2008)",

}

Minimum blocking sets of circles for a set of lines in the plane. / Jovanovic, N.; Korst, J.H.M.; Janssen, A.J.E.M.

Proceedings 20th Canadian Conference on Computational Geometry (CCCG'08, Montréal, Québec, Canada, August 13-15, 2008). 2008. p. 91-94.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Minimum blocking sets of circles for a set of lines in the plane

AU - Jovanovic, N.

AU - Korst, J.H.M.

AU - Janssen, A.J.E.M.

PY - 2008

Y1 - 2008

N2 - A circle C is occluded by a set of circles C1; : : : ;Cn if every line that intersects C also intersects at least one of the Ci; i = 1; : : : ; n. In this paper, we focus on determining the minimum number of circles that occlude a given circle assuming that all circles have radius 1 and their mutual distance is at least d. As main contribution of this paper, we present upper and lower bounds on this minimal number of circles for 2 =d =4, as well as the algorithms we used to derive them.

AB - A circle C is occluded by a set of circles C1; : : : ;Cn if every line that intersects C also intersects at least one of the Ci; i = 1; : : : ; n. In this paper, we focus on determining the minimum number of circles that occlude a given circle assuming that all circles have radius 1 and their mutual distance is at least d. As main contribution of this paper, we present upper and lower bounds on this minimal number of circles for 2 =d =4, as well as the algorithms we used to derive them.

M3 - Conference contribution

SP - 91

EP - 94

BT - Proceedings 20th Canadian Conference on Computational Geometry (CCCG'08, Montréal, Québec, Canada, August 13-15, 2008)

ER -