This talk will introduce the notion of social distance width (SDW) in geometric domains, to model and quantify the ability for two or more agents to maintain social distancing while moving within their respective, possibly shared, domains. Depending on whether the agents’ motion is continuous or discrete, I will first focus on the social distance width of two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. I will then define the social distance width of a polygon, which measures the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon, and outline algorithms to compute it. If time permits, I will also describe other interesting variants where the agents move on a graph, and summarize hardness results and algorithms for both general and special (e.g., trees) types of graphs. I hope the audience will find more connections between this proposed measure and existing work in computational geometry, leading to research on interesting open problems.
Based on ongoing work with Joe Mitchell, Valentin Polishchuk, and Omrit Filtser.