Geometry Seminar

---

A variant of backwards analysis applicable to order-dependent sets

Speaker: Martin Suderland, NYU

Location: Warren Weaver Hall 1314

Date: Tuesday, March 26, 2024, 6 p.m.

Synopsis:

Backwards analysis is a simple, yet powerful technique used in analyzing the expected performance of randomized algorithms: a randomized incremental algorithm is seen as if it were running backwards in time, from output to input [Seidel 1993]. To be applicable, a key requirement is that the algorithm's output is independent of the randomization order. This needs to hold even for intermediate structures, assuming the same set of elements has been processed. We promote a variant, which can be applied to algorithms with order-dependent output. This variant of backwards analysis was introduced by [Junginger and Papadopoulou, DCG 2023]. As an example, we use the randomized incremental triangulation of a point set in ℝ^d, a generalization of Quicksort in higher dimensions, which has been cited by Seidel as a negative example, where backwards analysis could not be applied. We prove that the expected running time of this algorithm is O(n log n). This is joint work with Evanthia Papadopoulou.

YouTube recording: https://youtu.be/_7IpUCBRAng

Notes:

In person or on Zoom.  See seminar mailing list for Zoom URL or contact Boris Aronov