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 language English 6 Published - 2012 Yes

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.