[Colloquium] 11/12 TTIC Colloquium: Sariel Har-Peled, University of Illinois at Urbana-Champaign

[Mary Marre via Colloquium]

*When:    *  Monday, November 12th at 11:00 am



*Where:     *TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who:        *Sariel Har-Peled, University of Illinois at Urbana-Champaign


*Title:*        On Locality-Sensitive Orderings and their Applications

*Abstract:*  For any constant d and parameter ε>0, we show the
existence of (roughly)
1/ε^d orderings on the unit cube [0,1)^d, such that any two points
p,q∈[0,1)^d that are close together under the Euclidean metric are "close
together" in one of these linear orderings in the following sense: the only
points that could lie between p and q in the ordering are points with
Euclidean distance at most ε∥p−q∥ from p or q. These orderings are
extensions of the Z-order, and they can be efficiently computed.
Functionally, the orderings can be thought of as a replacement to quadtrees
and related structures (like well-separated pair decompositions). We use
such orderings to obtain surprisingly simple algorithms for a number of basic
problems in low-dimensional computational geometry, including (i) dynamic
approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic
approximate minimum spanning trees, (iv) static and dynamic fault-tolerant
spanners, and (v) approximate nearest neighbor search.

Joint work with Timothy M. Chan and Mitchell Jones
https://arxiv.org/abs/1809.11147


*Host: * Avrim Blum <avrim at ttic.edu>


For more information on the colloquium series or to subscribe to the
mailing list,please see http://www.ttic.edu/colloquium.php




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20181105/a8c2670d/attachment-0001.html>