spencer@eecs.umich.edu (Spencer W. Thomas) (09/20/90)
I'm looking for cheap way to solve the following problem: I've got a "randomly" distributed set of K points in the unit cube. I would like to estimate, for each point in my set, a bounding box surrounding the Voronoi cell for that point. Note that since I am limiting my space to the unit cube, all the cells will be finite. If I can't get a bounding box, I'd be satisfied with a diameter estimate instead. In order for this to be helpful, I need an algorithm that is at worst O(K log K). The estimate doesn't have to be tight, as long as it decreases proportionately with the size of the cell. Thanks. -- =Spencer W. Thomas EECS Dept, U of Michigan, Ann Arbor, MI 48109 spencer@eecs.umich.edu 313-936-2616 (8-6 E[SD]T M-F)