Path: utzoo!attcan!uunet!samsung!sol.ctr.columbia.edu!srcsip!msi-s0.msi.umn.edu!umeecs!zip!spencer From: spencer@eecs.umich.edu (Spencer W. Thomas) Newsgroups: comp.graphics Subject: Voronoi cell diameter estimation. Message-ID: Date: 20 Sep 90 16:25:32 GMT Sender: news@zip.eecs.umich.edu Distribution: comp Organization: University of Michigan EECS Dept Lines: 18 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)