4th Workshop on Uncertainty in Computational Geometry
27 June 2025 in Kanazawa, Japan
There is a growing need for algorithms that utilize and operate gracefully under data uncertainty. The sources of data uncertainty can vary widely, from measurement noise to missing information and strategic randomness, among others. Several computational geometry researchers have explored a variety of input models and problem-specific approaches, demonstrating a breadth of interest and scope. This research area, however, is still growing, and benefits from a broader exchange of ideas on, probabilistic vs. deterministic, discrete vs. continuous, and static vs. dynamic, models of input uncertainty.
The workshop is planned to be held in person at CGweek'25 in Kanazawa.
Abstract: In this talk we consider a transportation problem in a setting different from the conventional centralized one. Inventory or demand quantities for various commodities are specified at each warehouse. Warehouses and roads connecting them are represented as nodes and edges of a graph, respectively. We use many vehicles, moving around only locally instead of globally to carry commodities to fulfill demands at warehouses by visiting neighbors. We assume a vehicle at each node and a two-way transportation in which a vehicle carries commodities from a warehouse to an adjacent warehouse and then brings other commodities back to the warehouse. In this scenario we consider the problem of deciding whether there is a single round of two-way trips of those vehicles that fulfill all demands. What happens if we introduce uncertainty in the amounts of supplies and demands?
Abstract: Ensemble analysis plays a crucial role in understanding the inherent uncertainty in real-world phenomena, and visualization serves as an effective tool aiding this process. We are working toward understanding and incorporating uncertainty into geometric and topological descriptors to effectively reason about their underlying data. In this talk, we will discuss a number of recent efforts in the context of uncertainty visualization, spanning applications in neuron morphology to asteroid trajectories.
Abstract: A 1.5D imprecise terrain is an x-monotone polyline with fixed x- coordinates, but the y-coordinate of each vertex is not fixed and is con- strained to be in a given vertical interval. A 2.5D imprecise terrain is a triangulation with fixed x and y-coordinates, but the z- coordinate of each vertex is constrained to a given vertical interval. Given an imprecise terrain with n intervals, the optimistic shortest watchtower problem asks for a realization T such that the height of the shortest vertical line segment whose lower endpoint lies on T and upper endpoint can see the entire terrain is minimized. In this talk, we present a linear time algorithm to solve the 1.5D optimistic shortest watchtower problem exactly and we give an O(1/\eplison n^3) time additive PTAS, i.e., with at most an error of \epsilon on top of the optimal solution, for the 2.5D discrete version of the problem (when the tower must lie on a vertex of T). We also share several open problems relating imprecision and visibility.
Some of this work is published here, and we recently submitted a paper describing the additional results in the abstract.
Abstract: Many modern computational applications are characterized by two qualities: data sets are massive and they vary over time. A fundamental, yet challenging, question is how to maintain some combinatorial structure that is a function of such a data set. Single-shot algorithms may be too slow, and common dynamic algorithms, which support explicit requests for insertions and deletions, may not be applicable because structural changes are unseen by the algorithm. Anagnostopoulos et al. introduced the evolving data framework to handle such data sets. Therein, the structure continuously varies over time through the unseen actions of an evolver, which makes small, stochastic changes to the data set. The algorithm can probe the current state locally through an oracle, with whose aid it attempts to maintain a hypothesis that is as close as possible to its actual state, at all times. The similarity between the hypothesis and current state is measured through some distance function. However, most of the previous research in this framework, has been restricted to simple problems like sorting, and ranking over purely combinatorial structures. The aim of our research is to process geometric data, and maintain geometric structures in an evolving data scenario.
Abstract: Geometric hitting set problems, in which we seek a smallest set of points that collectively hit a given set of ranges, are ubiquitous in computational geometry. Most often, the set is discrete and is given explicitly. We propose new variants of these problems, dealing with continuous families of convex polyhedra, and show that they capture decision versions of the two-level finite adaptability problem in robust optimization. We show that these problems can be solved in strongly polynomial time when the size of the hitting/covering set and the dimension of the polyhedra and the parameter space are constant. We also show that the hitting set problem can be solved in strongly quadratic time for one-parameter families of convex polyhedra in constant dimension. This leads to new tractability results for finite adaptability that are the first ones with so-called left-hand-side uncertainty, where the underlying problem is non-linear.
The manuscript is available here.
| Time | |
|---|---|
| 14:10–14:15 | Introductory Remarks |
| 14:15–14:55 | Tetsuo Asano Transportation Problem Using Localized Transportations |
| 14:55–15:00 | Short Break |
| 15:00–15:40 | Bei Wang Visualizing Structural Uncertainty of Ensemble Data: from Neuron Morphology to Asteroid Trajectories |
| 15:40–16:00 | Break |
| 16:00–16:20 | Bradley McCoy Imprecise Watchtowers |
| 16:20–16:40 | David Mount Algorithms for Processing Evolving Geometric Data |
| 16:40–17:00 | Sarah Wajsbrot Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization |
The organizers can be contacted at cgweekuncertainty@gmail.com.