### Abstract

Original language | English |
---|---|

Number of pages | 6 |

Publication status | Published - 2012 |

Externally published | Yes |

### Fingerprint

### Cite this

}

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

Research output: Other contribution › Other 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 -