tag:blogger.com,1999:blog-6555947.post6841619056351944577..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Computing the size of a convex hullSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-6555947.post-10743741834652025102007-01-18T12:30:00.000-07:002007-01-18T12:30:00.000-07:00I've added in a ref to the Ben-Or paper (the ACM s...I've added in a ref to the Ben-Or paper (the ACM site was down, so the link is from DBLP)Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-27020323609486705162007-01-18T08:57:00.000-07:002007-01-18T08:57:00.000-07:00It will be really good, if the bloggers give the f...It will be really good, if the bloggers give the full reference. It will be easier for people like me, that are not experts to follow more easily the discussion. <br />For example, what is the ref for<br />"Example 5 in the Ben-Or result (which applies to order d decision trees)"<br /><br />I know. Silly question. But on the other hand, it a silly question is better than never know the answer :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-68142304442667396632007-01-17T10:57:00.000-07:002007-01-17T10:57:00.000-07:00I don't know if there is one. I'm still waiting fo...I don't know if there is one. I'm still waiting for Jeff to write his monograph on lower bounds: hopefully then we'll have a nice reference ;)Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-39958299942227146942007-01-17T07:42:00.000-07:002007-01-17T07:42:00.000-07:00BTW, what is a good introductory text for the alge...BTW, what is a good introductory text for the algebraic decision tree model, and for the other models of computations?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-25068083890469424302007-01-16T10:14:00.000-07:002007-01-16T10:14:00.000-07:00I can't put my finger on what I find distasteful a...I can't put my finger on what I find distasteful about the reduction from element uniqueness. Maybe it's the way in which it conflates finding the set of vertices and their number. I'd have preferred a general bound that said that checking if there were $h$ vertices is hard, or even distinguishing between k and k+1, for k = w(1), and o(log n)Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-12545919320875476002007-01-16T08:46:00.000-07:002007-01-16T08:46:00.000-07:00The Ω(n log n) lower bound for "Are all n points e...The Ω(n log n) lower bound for "Are all n points extreme?" that Christos describes also holds if you assume (or require) that the points are distinct, by reduction from the <i>integer</i> element uniqueness problem. The idea is to put the points <i>almost</i> on the parabola. Put the ith point at coordinates (x_i, x_i^2 + iε), for some sufficiently small rational ε. Then the convex hull has n vertices if and only if the (integer) x-coordinates are distinct.<br /><br />In the algebraic decision tree model, you can reduce from the standard (real) element uniqueness problem by taking ε to be a formal, symbolic infinitesimal.Jeff Ericksonhttp://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-91753427841760401132007-01-16T01:46:00.000-07:002007-01-16T01:46:00.000-07:00By the way, the element uniqueness problem has an ...By the way, the element uniqueness problem has an Omega(nlogn) lower bound even in the algebraic decision tree model, so the\<br /> same idea would carry over to the number of corners of the convex hull.<br /><br />- Christos Levcopoulos, Lund, SwedenChristos Levcopoulosnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-47105308452739490532007-01-15T08:11:00.000-07:002007-01-15T08:11:00.000-07:00... and perhaps I should clarify: we DON'T have to...... and perhaps I should clarify: we DON'T have to check that the points lie on the y=x^2 parabola. As far as our model concerns, we will only see that whenever we check whether a point p3 lies above or below a line (p1,p2), the result will only be consistent with respect to the respective x-coordinates of the points p1, p2 and p3. So the lower bound holds for our model.<br /><br />- Christos Levcopoulos<br /> Lund UniversityChristos Levcopoulosnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-12873977657804013122007-01-15T07:33:00.000-07:002007-01-15T07:33:00.000-07:00Hello,
one could consider a simple,
extended comp...Hello,<br />one could consider a simple, <br />extended comparison-based <br />model where, for example, in <br />addition to usual comparisons <br />between real numbers, one can <br />perform the following type<br />of operations: given three points <br />p1, p2 and p3, test <br />whether p3 lies above, below or <br />on the line defined<br />by p1 and p2 (if this line is <br />not vertical, of course). <br />Such a model suffices to <br />compute convex hulls in O(nlogn) <br />time. It should not be difficult <br />to show that in such a <br />model you need Omega(nlogn) time <br />in the worst case to <br />determine the number of corners <br />of the convex hull by <br />standard methods. <br /><br />If the only concern is the number <br />of corners of the convex hull, <br />then we can, for example,<br />consider the special case where <br />all input points<br />lie on the parabola y=x^2. Then <br />the number of corners of the <br />convex hull is equal to n iff<br />no two input points have the same x-coordinate.<br />Hence, we derive an Omega(nlogn) <br />lower bound from the <br />element-uniqueness problem.<br /><br />With regards,<br />- Christos Levcopoulos<br /> Lund University, SwedenChristos Levcopoulosnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-52369485741194518972007-01-14T23:23:00.000-07:002007-01-14T23:23:00.000-07:00This question seems hard. You can get a good estim...This question seems hard. You can get a good estimate of the number of vertices in the first O(log n) levels, by randomly choosing each point with probability 1/log n, and then computing the convex hull of the sample, using the Clarkson technique to bound the number of vertices. You get an Omega type bound, which might be useful for something, and then maybe not. See the work of Malmuley on ray shooting.<br /><br />now, does this has any connection to your question?<br /><br />--SAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-69276525857176504642007-01-14T20:57:00.000-07:002007-01-14T20:57:00.000-07:00so much for trying to post something technical. Le...so much for trying to post something technical. Let's try again.<br /><br />As Jeff points out, I misspoke: it's not a "comparison model", but a quadratic decision tree model in which the lower bound holds. <br /><br />Ben-Or does appear to say that checking if a convex hull contains n vertices has a lower bound; but I am confused, because the result cites Yao's result for quadratic decision trees, and Yao's result doesn't say anything about the size, but about the specification of the actual set. <br /><br />Finally, when I say "size", I mean "cardinality". I'm not talking about approximating the area, which as Jeff points out can be done by using approximate extent technology.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-62760019218308345012007-01-14T11:19:00.000-07:002007-01-14T11:19:00.000-07:00Bad geometer! No biscuit!
In the comparison mode...Bad geometer! No biscuit!<br /><br />In the comparison model, computing the convex hull takes at least Ω(n^213738912379) time, for the trivial reason YOU CAN'T DO IT AT ALL. Comparisons simply don't give you enough information to compute convex hulls.<br /><br />Yao proved the first Ω(n log n) lower bound for convex hulls by considering a model that is actually powerful enough to solve the problem!<br /><br />The answer to your question is no. It's fairly easy to compute a (1+ε)-approximation of the area in O(n/poly(ε)) time, using standard (ie, Sarielesque) approximation techniques.Jeff Ericksonhttp://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-44627449243933448602007-01-13T15:21:00.000-07:002007-01-13T15:21:00.000-07:00Nice new template :)Nice new template :)Mahdihttp://www.blogger.com/profile/02090790154745749807noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-3389349889370241182007-01-13T10:51:00.000-07:002007-01-13T10:51:00.000-07:00Since you mentined 3D hulls, there's a more recent...Since you mentined 3D hulls, there's a more recent result by Timothy and me that's achieving significantly better bounds:<br /><br /><i>Voronoi Diagrams in</i> n * 2^O(√lglg n) <i>Time</i>Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-3951754018559655872007-01-13T09:38:00.000-07:002007-01-13T09:38:00.000-07:00Maybe I'm missing something, but isn't this Exampl...Maybe I'm missing something, but isn't this Example 5 in the Ben-Or result (which applies to order d decision trees)? He attributes the quadratic decision tree lower bound to Yao.Anonymousnoreply@blogger.com