Finding shadows among disks
| Autor: | Jovanovic, N., Korst, J.H.M., Aleksovski, Z., Michiels, W.P.A.J., Lukkien, J.J., Aarts, E.H.L. |
|---|---|
| Přispěvatelé: | Mathematics and Computer Science, Security |
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: | |
| Zdroj: | Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, Prince Edward Island, Canada, August 8-10, 2012, 89-94 STARTPAGE=89;ENDPAGE=94;TITLE=Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, Prince Edward Island, Canada, August 8-10, 2012 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|