PhD Seminar • Algorithms and Complexity • Dispersion on Intervals: A Geometric ApproachExport this event to calendar

Wednesday, August 10, 2022 — 1:00 PM to 2:00 PM EDT

Please note: This PhD seminar will take place online.

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

Supervisor: Professor Anna Lubiw

In the dispersion problem for ordered intervals, the input is an ordered list of intervals on the real line, and the task is to select one point from each interval, such that the ordering of points along the line respects the given ordering of intervals and such that the points are “far apart” from each other.

Li and Wang (Discrete Applied Math., 2018) gave a linear time algorithm for dispersion on ordered intervals that maximizes the minimum distance between any two points. We give a simpler linear time algorithm for the stronger goal of maximizing the minimum distance, then maximizing the second minimum distance, and so on. Our algorithm transforms the problem into a shortest path problem in a simple polygon. The result is based on very elementary ideas and was published at SOSA 2021.

We also apply our geometric approach to the case of ordered intervals on a closed curve and some other variants of the problem where earlier techniques do not seem to be applicable. We also sketch (without details) some results in 2D dispersion (published at ESA 2021).

Joint work with Therese Biedl, Anna Lubiw, Peter Ralbovsky, and Graeme Stroud.


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

Location 
Online PhD Seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

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