Finding shadows among disks

N. Jovanovic, J.H.M. Korst, Z. Aleksovski, W.P.A.J. Michiels, J.J. Lukkien, E.H.L. Aarts

Research output: Other contributionOther research output

Abstract

Given a set of n non-overlapping unit disks in the plane, a line l is called blocked if it intersects at least one of the disks and a point p is called a shadow point if all lines containing p are blocked. In addition, a maximal closed set of shadow points is called a shadow region. We derive properties of shadow regions, and present an O(n^4) algorithm that outputs all shadow regions. We prove that the number of shadow regions is O(n^4) for some instances, which implies that the worst-case time complexity of the presented algorithm is optimal.
Original languageEnglish
Number of pages6
Publication statusPublished - 2012
Externally publishedYes

Fingerprint

Line
Closed set
Intersect
Unit Disk
Time Complexity
Imply
Output

Cite this

Jovanovic, N., Korst, J. H. M., Aleksovski, Z., Michiels, W. P. A. J., Lukkien, J. J., & Aarts, E. H. L. (2012). Finding shadows among disks.
Jovanovic, N. ; Korst, J.H.M. ; Aleksovski, Z. ; Michiels, W.P.A.J. ; Lukkien, J.J. ; Aarts, E.H.L. / Finding shadows among disks. 2012. 6 p.
@misc{38c763b9fec24683818b7ece613ec0ef,
title = "Finding shadows among disks",
abstract = "Given a set of n non-overlapping unit disks in the plane, a line l is called blocked if it intersects at least one of the disks and a point p is called a shadow point if all lines containing p are blocked. In addition, a maximal closed set of shadow points is called a shadow region. We derive properties of shadow regions, and present an O(n^4) algorithm that outputs all shadow regions. We prove that the number of shadow regions is O(n^4) for some instances, which implies that the worst-case time complexity of the presented algorithm is optimal.",
author = "N. Jovanovic and J.H.M. Korst and Z. Aleksovski and W.P.A.J. Michiels and J.J. Lukkien and E.H.L. Aarts",
year = "2012",
language = "English",
type = "Other",

}

Jovanovic, N, Korst, JHM, Aleksovski, Z, Michiels, WPAJ, Lukkien, JJ & Aarts, EHL 2012, Finding shadows among disks..

Finding shadows among disks. / Jovanovic, N.; Korst, J.H.M.; Aleksovski, Z.; Michiels, W.P.A.J.; Lukkien, J.J.; Aarts, E.H.L.

6 p. 2012, .

Research output: Other contributionOther research output

TY - GEN

T1 - Finding shadows among disks

AU - Jovanovic, N.

AU - Korst, J.H.M.

AU - Aleksovski, Z.

AU - Michiels, W.P.A.J.

AU - Lukkien, J.J.

AU - Aarts, E.H.L.

PY - 2012

Y1 - 2012

N2 - Given a set of n non-overlapping unit disks in the plane, a line l is called blocked if it intersects at least one of the disks and a point p is called a shadow point if all lines containing p are blocked. In addition, a maximal closed set of shadow points is called a shadow region. We derive properties of shadow regions, and present an O(n^4) algorithm that outputs all shadow regions. We prove that the number of shadow regions is O(n^4) for some instances, which implies that the worst-case time complexity of the presented algorithm is optimal.

AB - Given a set of n non-overlapping unit disks in the plane, a line l is called blocked if it intersects at least one of the disks and a point p is called a shadow point if all lines containing p are blocked. In addition, a maximal closed set of shadow points is called a shadow region. We derive properties of shadow regions, and present an O(n^4) algorithm that outputs all shadow regions. We prove that the number of shadow regions is O(n^4) for some instances, which implies that the worst-case time complexity of the presented algorithm is optimal.

M3 - Other contribution

ER -

Jovanovic N, Korst JHM, Aleksovski Z, Michiels WPAJ, Lukkien JJ, Aarts EHL. Finding shadows among disks. 2012. 6 p.