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: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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
Title of host publicationProceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, Prince Edward Island, Canada, August 8-10, 2012
Pages89-94
Publication statusPublished - 2012
Event24th Canadian Conference on Computational Geometry (CCCG 2012) - Charlottentown, Canada
Duration: 8 Aug 201210 Aug 2012
Conference number: 24
http://2012.cccg.ca/

Conference

Conference24th Canadian Conference on Computational Geometry (CCCG 2012)
Abbreviated titleCCCG
CountryCanada
CityCharlottentown
Period8/08/1210/08/12
Internet address

Fingerprint Dive into the research topics of 'Finding shadows among disks'. Together they form a unique fingerprint.

Cite this