There is a growing need for geometric algorithms that can gracefully operate under data uncertainty. The sources of data uncertainty can vary widely, from measurement noise to missing information and strategic randomness, among others. A number of researchers within computational geometry have explored a variety of data uncertainty models and problem-specific approaches, demonstrating a breadth of interest and scope. At SOCG 2016, the first installment of this workshop was organized by Pankaj Agarwal, Nirman Kumar, Ben Raichel and Subhash Suri. Since then the area has continued to expand, warranting another installment of the workshop to provide updates on previous topics, as well as to touch on new topics in uncertainty. The goal of the workshop is to provide a forum for computational geometers interested in this topic to learn about the current state of the art, stimulate discussions about new directions and challenges, and to foster collaborations. We also plan to more broadly survey the growth in the area of uncertainty and take stock of where the area is heading.
Friday, June 10 |
||
|---|---|---|
| Time | Speaker | Title/Slides |
| 14:30--14:40 | Maarten Löffler / Benjamin Raichel | Introduction and Overview |
| 14:45--15:25 | David Kirkpatrick | Query Strategies for Maintaining Low Potential Congestion/Interference Among Moving Entities |
| 15:30--16:00 | Coffee Break | |
| 16:00--16:40 | Mohammad Farshi | Imprecise Spanners |
| 16:45--17:25 | Kevin Buchin | Uncertain Trajectories |
| 17:30--18:00 | Maarten Löffler / Benjamin Raichel | Discussion |
Entities (imagine small spheres) moving continuously, but with bounded speed, in d-dimensional Euclidean space can realize a large variety of potential trajectories. If actual trajectories are not fully specified, by some modelling assumption or by continuous monitoring, then uncertainty in individual and relative entity locations at fixed points in time is unavoidable. Of course, some tasks involving the locations (or relative locations) of a collection of entities might be solvable at such fixed times even in the presence of (limited amounts of) uncertainty. So it is natural, especially where location queries are expensive, to try and formulate efficient strategies for entity queries that promise to reduce uncertainty to a degree that solutions are feasible at all points of time of interest.
Problems of this and closely related natures have been studied for a considerable time, forming part of a much broader literature considering query-based approaches to dealing with data uncertainty. This talk focuses on one approach that has met with considerable success over the past decade in dealing with potential congestion/interference, measured in several different ways, among collections of moving entities. Since actual congestion/interference (when locations are fully specified) might at times be high, it makes sense to evaluate any query scheme in terms of its competitiveness, over modest length time intervals, with the best (or luckiest) possible query scheme. The schemes that I will describe, including results presented at SoCG'13, EuroCG'14, SICOMP'16, SODA'19, and EuroCG'22, as well as recent unpublished work, are competitive even with clairvoyant query strategies (those that somehow know/guess the trajectories of all entities) with the same objective.
To be more concrete, the results apply to a collection of transmission sources, with associated broadcast ranges, moving in three dimensions. Two such entities, transmitting on the same channel, interfere if their broadcast ranges intersect. Uncertainty in the location of a transmission source effectively expands its broadcast range to a potential broadcast range. The chromatic number of the intersection graph of these potential broadcast ranges, one of our measures of potential congestion/interference, gives the minimum number of broadcast channels required to avoid transmission interference. Our query schemes provide adaptive, locally updated, channel assignment schemes that are competitive over time with any other such scheme in terms of the number of broadcast channels used with a fixed monitoring frequency or in terms of the monitoring frequency required to maintain interference-free transmission with a fixed number of channels.
Let t>1 be a real number. A geometric t-spanner is a geometric (Euclidean) graph for a point set in $\mathbb{R}^d$ with straight line segments between vertices such that the ratio of the shortest-path distance between every pair of vertices in the graph (with Euclidean edge lengths) to their actual Euclidean distance is at most t.
An imprecise point set is modeled by a set R of regions in $\mathbb{R}^d$. If one chooses a point inside each region of R, then the resulting point set is called a precise instance from R. An imprecise t-spanner for an imprecise point set R is a graph G=(R,E) such thatfor each precise instance S from R, graph G_S=(S,E_S), where E_S is the set of edges corresponding to E and S, is a t-spanner.
In this talk, we review the results (algorithms or hardness results) for constructing a t-spanner for a given imprecise point set.
There are many classical algorithms in computational geometry dealing with the analysis of curves and trajectories. It is typically assumed that the locations of points making up the trajectories are known precisely, which often does not suit real-life data.
Firstly, measurement uncertainty has to be taken into account. For instance in GPS data the measured location is inherently imprecise, and the real location is likely to be within a certain distance from the measurement. Secondly, between two consecutive measurements there is movement uncertainty. That is, the real location between measurements is unknown, and modeling trajectories as polygonal curves may be unrealistic.
In this talk I will focus on recent results on curve similarity and simplification taking into account measurement uncertainty. Further I will present some examples of results on movement uncertainty between measurements.