From: Venkatesan Guruswami (venkat@cs.washington.edu)
Date: Thu Mar 18 2004 - 08:41:35 PST
Special Theory Seminar
~~~~~~~~~~~~~~~~~~
TIME: Thursday, Mar 18, 11-11:50 am
PLACE: CSE 403
SPEAKER: Piotr Indyk, MIT
TITLE: Algorithms for Dynamic Geometric Problems over Data Streams
ABSTRACT:
The vast majority of known data structures use space at least linear
in the number of objects stored. Are there any interesting problems
that can be solved in sub-linear space? In this talk we present
several new results of this type, in the context of
geometric/spatial data. Our data structures support insertions and
deletions of points, as well as (approximate) queries about
geometric properties of the data, such as the value of the minimum
cost tree connecting the points, the minimum weight matching of the
points, and various clustering problems.
_______________________________________________
Theory-talks mailing list
Theory-talks@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Thu Mar 18 2004 - 08:41:56 PST