PhD Seminar • Algorithms and Complexity • The Visibility Center of a Simple PolygonExport this event to calendar

Thursday, July 7, 2022 — 2:00 PM to 3:00 PM EDT

Please note: This PhD seminar will be given online.

Anurag Murty Naredla, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Anna Lubiw

Two points in a polygon see each other if the line segment joining them does not exit the polygon. Based on this well-studied notion, we introduce the visibility center of a set of points inside a polygon — a point c such that the maximum geodesic distance from c to see any point in the set is minimized. For a simple polygon of n vertices and a set of m points inside it, we give an O((n + m) log (n + m)) time algorithm to find the visibility center. We find the visibility center of all points in a simple polygon in O(n log n) time.

Our algorithm reduces the visibility center problem to the problem of finding the geodesic center of a set of half-polygons inside a polygon, which is of independent interest. We give an O((n + k) log(n + k)) time algorithm for this problem, where k is the number of half-polygons.

Joint work with Anna Lubiw.


To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/98651937935.

Location 
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
  1. 2022 (167)
    1. August (26)
    2. July (23)
    3. June (17)
    4. May (20)
    5. April (24)
    6. March (22)
    7. February (16)
    8. January (19)
  2. 2021 (210)
    1. December (21)
    2. November (13)
    3. October (12)
    4. September (21)
    5. August (20)
    6. July (17)
    7. June (11)
    8. May (16)
    9. April (27)
    10. March (20)
    11. February (13)
    12. January (19)
  3. 2020 (217)
  4. 2019 (255)
  5. 2018 (217)
  6. 2017 (36)
  7. 2016 (21)
  8. 2015 (36)
  9. 2014 (33)
  10. 2013 (23)
  11. 2012 (4)
  12. 2011 (1)
  13. 2010 (1)
  14. 2009 (1)
  15. 2008 (1)