[Colloquium] REMINDER: 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>*


On Sun, Nov 11, 2018 at 6:30 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>*
>
>
> 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/20181112/398e72ec/attachment-0001.html>