tag:blogger.com,1999:blog-6555947.post6264195547999229033..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: The "Voronoi trick"Suresh Venkatasubramaniannoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-6555947.post-18129758605012725962008-04-04T04:59:00.000-06:002008-04-04T04:59:00.000-06:00Hi, I think this post very interesting and enlight...Hi, I think this post very interesting and enlightening. I came across your article after doing a search on Voronois diagrams. Can you please explain why "for a set of n points in d dimensions, there are roughly n^{kd} distinct Voronoi partitions"? Perhaps it comes from choosing k points to be in distinct Voronoi regions? But I don't see how the dimension of the space comes into play.<BR/><BR/>I tried looking at the Inaba et al reference but couldn't understand their proof. I also don't see how you can enumerate all distinct Voronois partitions in polynomial time.<BR/><BR/>Thank you very much.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-6419247265892201172007-09-27T03:44:00.000-06:002007-09-27T03:44:00.000-06:00What you are talking about here sounds very simila...What you are talking about here sounds very similar to the `segmentation problems' of <A HREF="http://web.umr.edu/~thakurk/2005-01-01-cs455/majors1.pdf" REL="nofollow">Kleinberg et al</A>. In particular, the Price Segmentation problem is as follows: A client would buy a quantity q(p)=a_i-p b_i if the price is p. The constants a_i and b_i describe customer i. You can choose for each client what price to use when selling but you can only choose out of k predefined possibilities. (Say, because you need to prepare in advance some documentation arguing why that price is fair.) What should be the k prices? There are two variants of the problem: one considers k given and one allows you to choose the optimum k.rgrighttp://www.blogger.com/profile/02991214367108471744noreply@blogger.com