Friday, October 29, 2021 - 11:00 to 12:30
SCHOOL OF COMPUTER SCIENCE – Colloquium Series
The School of Computer Science at the University of Windsor is pleased to present…
Colloquium Presentation #5 by Mr. Anurag Murty Naredla
Date: Friday October 29, 2021
Time: 11:00am – 12:30pm
Meeting URL:https://us06web.zoom.us/j/84169502868?from=addon
Passcode: If interested in attending this event, contact the Graduate Secretary at csgradinfo@uwindsor.ca with suffient notice before the event to obtain the passcode.
Abstract:
We will discuss two natural problems: the first one addresses social distancing (on a line), and the second problem is related to guarding art galleries.
In the social distancing problem (formally called the Dispersion Problem on Intervals), the setup is the following: N people stand in a queue and have preferred intervals in which they want to stand.
We wish to locate them so that: (i) they get a spot within their preferred interval, (ii) their queue order is maintained, and (iii) the closest pair is as far apart as possible. We describe a geometric transformation that provides an optimal linear-time algorithm for the problem. We will also briefly touch upon some extensions to higher dimensions. This is joint work with Therese Biedl, Anna Lubiw, Peter Ralbovsky, and Graeme Stroud.
In the guarding problem, we will discuss the natural problem of optimally placing a single guard (or an automated observer) inside a polygonal art gallery. The optimal location, which we refer to as the visibility center, is a point from which the maximum geodesic distance to see any point in the polygon is as low as possible. We will sketch the ideas for an O(n log n) time algorithm for finding the visibility center. This is joint work with Anna Lubiw.
Biography:
Anurag Murty Naredla is a Ph.D. student at the University of Waterloo, supervised by Anna Lubiw. He is interested in algorithms and data structures, especially ones that have a geometric flavor. Other interests include graph theory and combinatorics.
5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716 csgradinfo@uwindsor.ca (working remotely)