### Abstract

We show that the region lit by a point fight source inside a simple n-gon after at most k reflections off the boundary has combinatorial complexity O(n^{2k}), for any k > 1. A lower bound of Ω((n/k)^{2k}) is also established which matches the upper bound for any fixed k. A simple near-optimal algorithm for computing the illuminated region is presented, which runs in O(n^{2k} log n) time and O(n^{2k}) space for any k>1.

Original language | English (US) |
---|---|

Title of host publication | Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings |

Editors | Rolf Karlsson, Andrzej Lingas |

Publisher | Springer Verlag |

Pages | 284-295 |

Number of pages | 12 |

ISBN (Print) | 3540614222, 9783540614227 |

DOIs | |

State | Published - 1996 |

Event | 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 - Reykjavik, Iceland Duration: Jul 3 1996 → Jul 5 1996 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1097 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 |
---|---|

Country | Iceland |

City | Reykjavik |

Period | 7/3/96 → 7/5/96 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Visibility with multiple reflections'. Together they form a unique fingerprint.

## Cite this

Aronov, B., Davis, A. R., Dey, T. K., Pal, S. P., & Chithra Prasad, D. (1996). Visibility with multiple reflections. In R. Karlsson, & A. Lingas (Eds.),

*Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings*(pp. 284-295). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1097). Springer Verlag. https://doi.org/10.1007/3-540-61422-2_139