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 contribution

1 Citation (Scopus)

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 Dive into the research topics of 'Finding shadows among disks'. Together they form a unique fingerprint.

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