<div dir="ltr"><div><div class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-gE gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-iv gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-gt" style="padding:10px 0px 3px"><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12.8px;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b>When:    </b>  Monday, November 12th at 11:00 am</font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12.8px;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12.8px;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b>Where:     </b>TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12.8px;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><b>Who:        </b></font><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Sariel Har-Peled</span></font><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">,</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">University</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">of Illinois at</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">Urbana</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">-</span><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">Champaign</span></p><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><br></font></div></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><b>Title:</b>        </font><span style="font-size:small">On Locality-Sensitive Orderings and their Applications</span><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><div><br></div><div><b>Abstract:</b>  <span style="font-size:small;font-family:Arial,Helvetica,sans-serif">For any constant d and parameter ε>0, we show the existence of </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">(roughly) 1/ε^d orderings on the unit cube [0,1)^d, such that any </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">two points p,q∈[0,1)^d that are close together under the Euclidean </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">metric are "close together" in one of these linear orderings in</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small"> the following sense: the only points that could lie between p and </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">q in the ordering are points with Euclidean distance at most </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">ε∥p−q∥ from p or q. These orderings are extensions of the Z-order, </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">and they can be efficiently computed. Functionally, the orderings </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">can be thought of as a replacement to quadtrees and related </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">structures (like well-separated pair decompositions). We use such </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">orderings to obtain surprisingly simple algorithms for a number of </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">basic problems in low-dimensional computational geometry, </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">including (i) dynamic approximate bichromatic closest pair, (ii) </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">dynamic spanners, (iii) dynamic approximate minimum spanning </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">trees, (iv) static and dynamic fault-tolerant spanners, and (v) </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">approximate nearest neighbor search.</span></div></font><br style="font-size:small"><span style="font-size:small">Joint work with Timothy M. Chan and Mitchell Jones</span><font face="arial, helvetica, sans-serif"><div><a href="https://arxiv.org/abs/1809.11147" rel="noreferrer" target="_blank" style="font-family:Arial,Helvetica,sans-serif;font-size:small">https://arxiv.org/abs/1809.11147</a>  <br></div><div><br></div><div><br></div></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><b>Host: </b> <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><br></div><font face="arial, helvetica, sans-serif"><font style="font-size:12.8px"><span style="font-kerning:none">For more information on the <span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-m_37711595404184628gmail-m_-8366621373355229216gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-il">colloquium</span></span></span></span></span></span></span> series or to subscribe to the mailing list,please </span>see <a href="http://www.ttic.edu/colloquium.php" target="_blank">http://www.ttic.edu/<span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="gmail-m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-il">colloquium</span></span></span></span></span></span>.php</a></font> </font><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br class="gmail-Apple-interchange-newline"></font><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr">On Sun, Nov 11, 2018 at 6:30 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-gE m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-iv m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-gt" style="padding:10px 0px 3px"><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12.8px;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b>When:    </b>  Monday, November 12th at 11:00 am</font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12.8px;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12.8px;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b>Where:     </b>TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;font-size:12.8px;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><b>Who:        </b></font><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Sariel Har-Peled</span></font><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">,</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">University</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">of Illinois at</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">Urbana</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">-</span><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">Champaign</span></p><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><br></font></div></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><b>Title:</b>        </font><span style="font-size:small">On Locality-Sensitive Orderings and their Applications</span><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><div><br></div><div><b>Abstract:</b>  <span style="font-size:small;font-family:Arial,Helvetica,sans-serif">For any constant d and parameter ε>0, we show the existence of </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">(roughly) 1/ε^d orderings on the unit cube [0,1)^d, such that any </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">two points p,q∈[0,1)^d that are close together under the Euclidean </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">metric are "close together" in one of these linear orderings in</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small"> the following sense: the only points that could lie between p and </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">q in the ordering are points with Euclidean distance at most </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">ε∥p−q∥ from p or q. These orderings are extensions of the Z-order, </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">and they can be efficiently computed. Functionally, the orderings </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">can be thought of as a replacement to quadtrees and related </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">structures (like well-separated pair decompositions). We use such </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">orderings to obtain surprisingly simple algorithms for a number of </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">basic problems in low-dimensional computational geometry, </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">including (i) dynamic approximate bichromatic closest pair, (ii) </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">dynamic spanners, (iii) dynamic approximate minimum spanning </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">trees, (iv) static and dynamic fault-tolerant spanners, and (v) </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">approximate nearest neighbor search.</span></div></font><br style="font-size:small"><span style="font-size:small">Joint work with Timothy M. Chan and Mitchell Jones</span><font face="arial, helvetica, sans-serif"><div><a href="https://arxiv.org/abs/1809.11147" rel="noreferrer" style="font-family:Arial,Helvetica,sans-serif;font-size:small" target="_blank">https://arxiv.org/abs/1809.11147</a>  <br></div><div><br></div><div><br></div></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><b>Host: </b> <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><br></div><font face="arial, helvetica, sans-serif"><font style="font-size:12.8px"><span style="font-kerning:none">For more information on the <span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-m_37711595404184628gmail-m_-8366621373355229216gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-il">colloquium</span></span></span></span></span></span></span> series or to subscribe to the mailing list,please </span>see <a href="http://www.ttic.edu/colloquium.php" target="_blank">http://www.ttic.edu/<span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="m_-2278336177098959175gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-il">colloquium</span></span></span></span></span></span>.php</a></font> </font><div><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr"><br></div><br class="m_-2278336177098959175gmail-Apple-interchange-newline"><div><div dir="ltr" class="m_-2278336177098959175gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br><br><div class="gmail_quote"><div dir="ltr">On Mon, Nov 5, 2018 at 5:24 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div dir="ltr"><div><div class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-gE m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-iv m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_4176080224522608772gmail-gt" style="padding:10px 0px 3px"><p class="MsoNormal" style="font-size:12.8px;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b>When:    </b>  Monday, November 12th at 11:00 am</font></p><p class="MsoNormal" style="font-size:12.8px;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="font-size:12.8px;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b>Where:     </b>TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></p><p class="MsoNormal" style="font-size:12.8px;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><b>Who:        </b></font><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Sariel Har-Peled</span></font><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">,</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span class="m_-2278336177098959175m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">University</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">of Illinois at</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> </span><span class="m_-2278336177098959175m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">Urbana</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">-</span><span class="m_-2278336177098959175m_3361278369988668236gmail-il" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">Champaign</span></p><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><br></font></div></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><b>Title:</b>        </font><span style="font-size:small">On Locality-Sensitive Orderings and their Applications</span><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><div><br></div><div><b>Abstract:</b>  <span style="font-size:small;font-family:Arial,Helvetica,sans-serif">For any constant d and parameter ε>0, we show the existence of </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">(roughly) 1/ε^d orderings on the unit cube [0,1)^d, such that any </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">two points p,q∈[0,1)^d that are close together under the Euclidean </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">metric are "close together" in one of these linear orderings in</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small"> the following sense: the only points that could lie between p and </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">q in the ordering are points with Euclidean distance at most </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">ε∥p−q∥ from p or q. These orderings are extensions of the Z-order, </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">and they can be efficiently computed. Functionally, the orderings </span><span style="font-family:Arial,Helvetica,sans-serif;font-size:small">can be thought of as a replacement to quadtrees and related </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">structures (like well-separated pair decompositions). We use such </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">orderings to obtain surprisingly simple algorithms for a number of </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">basic problems in low-dimensional computational geometry, </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">including (i) dynamic approximate bichromatic closest pair, (ii) </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">dynamic spanners, (iii) dynamic approximate minimum spanning </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">trees, (iv) static and dynamic fault-tolerant spanners, and (v) </span><span style="font-size:small;font-family:Arial,Helvetica,sans-serif">approximate nearest neighbor search.</span></div></font><br style="font-size:small"><span style="font-size:small">Joint work with Timothy M. Chan and Mitchell Jones</span><font face="arial, helvetica, sans-serif"><div><a href="https://arxiv.org/abs/1809.11147" rel="noreferrer" style="font-family:Arial,Helvetica,sans-serif;font-size:small" target="_blank">https://arxiv.org/abs/1809.11147</a>  <br></div><div><br></div><div><br></div></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><b>Host: </b> <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><br></div><font face="arial, helvetica, sans-serif"><font style="font-size:12.8px"><span style="font-kerning:none">For more information on the <span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-m_37711595404184628gmail-m_-8366621373355229216gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-il">colloquium</span></span></span></span></span></span></span> series or to subscribe to the mailing list,please </span>see <a href="http://www.ttic.edu/colloquium.php" target="_blank">http://www.ttic.edu/<span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="m_-2278336177098959175m_3361278369988668236gmail-m_3239492643088026663gmail-il">colloquium</span></span></span></span></span></span>.php</a></font> </font><div><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr"><br></div><div dir="ltr"><br></div><br class="m_-2278336177098959175m_3361278369988668236gmail-Apple-interchange-newline"><div><div dir="ltr" class="m_-2278336177098959175m_3361278369988668236gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div></div>