Loading...

How to extend visibility polygons by mirrors to cover invisible segments

Vaezi, A ; Sharif University of Technology | 2017

354 Viewed
  1. Type of Document: Article
  2. DOI: 10.1007/978-3-319-53925-6_4
  3. Publisher: Springer Verlag , 2017
  4. Abstract:
  5. Given a simple polygon P with n vertices, the visibility polygon (V P) of a point q (V P(q)), or a segment (formula present) (V P(pq)) inside P can be computed in linear time. We propose a linear time algorithm to extend V P of a viewer (point or segment), by converting some edges of P into mirrors, such that a given non-visible segment (formula present) can also be seen from the viewer. Various definitions for the visibility of a segment, such as weak, strong, or complete visibility are considered. Our algorithm finds every edge such that, when converted to a mirror, makes (formula present) visible to our viewer. We find out exactly which interval of (formula present) becomes visible, by every edge middling as mirror, all in linear time. © Springer International Publishing AG 2017
  6. Keywords:
  7. Clustering algorithms ; Geometry ; Visibility ; Linear time ; Linear-time algorithms ; Simple polygon ; Mirrors
  8. Source: 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017, 29 March 2017 through 31 March 2017 ; Volume 10167 LNCS , 2017 , Pages 42-53 ; 03029743 (ISSN); 9783319539249 (ISBN)
  9. URL: https://link.springer.com/chapter/10.1007/978-3-319-53925-6_4