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.
|Title of host publication||Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, Prince Edward Island, Canada, August 8-10, 2012|
|Publication status||Published - 2012|
|Event||24th Canadian Conference on Computational Geometry (CCCG 2012) - Charlottentown, Canada|
Duration: 8 Aug 2012 → 10 Aug 2012
Conference number: 24
|Conference||24th Canadian Conference on Computational Geometry (CCCG 2012)|
|Period||8/08/12 → 10/08/12|