[Colloquium] REMINDER: 11/12 TTIC Colloquium: Sariel Har-Peled, University of Illinois at Urbana-Champaign
Mary Marre via Colloquium
colloquium at mailman.cs.uchicago.edu
Sun Nov 11 18:30:26 CST 2018
*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>*
On Mon, Nov 5, 2018 at 5:24 PM Mary Marre <mmarre at ttic.edu> wrote:
> *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/20181111/4512b120/attachment-0001.html>
More information about the Colloquium
mailing list