APPROXIMATE VORONOI CELLS OVER DATA STREAMS

MPhil Thesis Defence


Title: "APPROXIMATE VORONOI CELLS OVER DATA STREAMS"

By

Mr. Yiu Wai CHAN


Abstract

Given a positive real parameter ε, we consider the problem of maintaining 
an ε-approximate Voronoi cell of a fixed point p with respect to a stream 
S of points in d dimensions. More precisely, we show how to maintain a 
subset of S, such that the convex polytope induced by the intersection of 
bisector halfspaces between p and points in this subset is an 
ε-approximate Voronoi cell. Our algorithm uses O (1/ε(d-1)/2 log (1/ε)) 
storage and O (1/ε(d-1)/2) time per insertion. This significantly improves 
existing results under the data stream model. Our result is optimal in 
space up to a logarithmic factor and matches the best known result in the 
traditional static model.


Date:			Tuesday, 20 August 2013

Time:			3:30pm - 5:30pm

Venue:			Room 3501
 			Lifts 25/26

Committee Members:	Dr. Sunil Arya (Supervisor)
 			Prof. Siu-Wing Cheng (Chairperson)
 			Prof. Mordecai Golin


**** ALL are Welcome ****