Talk:Dynamic convex hull
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Inanity
[edit]Well, it was not inanity. It was careless unfinished writing. The lower bound is Omega(n) if one is required to report a convex hull in traditional way, as a convex polygon. I am not completely senile yet (although steadily moving in this direction :-) `'юзырь:mikka 01:29, 16 June 2007 (UTC)
New paper
[edit]Erik D. Demaine and Mihai Pǎtraşcu, ``Tight Bounds for Dynamic Convex Hull Queries (Again), in Proceedings of the 23rd Annual ACM Symposium on Computational Geometry (SoCG 2007), Gyeongju, South Korea, June 6-8, 2007
It's not on Erik's web site yet, but should be available through ACM when ACM's web site comes back up. —David Eppstein 01:51, 16 June 2007 (UTC)
"The convex hull becomes a triangle"?
[edit]"It is easy to construct an example for which the convex hull contains all input points, but after the insertion of a single point the convex hull becomes a triangle."
What is this supposed to mean? I cannot come up with any interpretation that makes sense.
- Consider a circular arc, entirely contained within an isosceles triangle and stretching from one end of the base of the triangle to the other end. Start with a set of input points equally spaced on this arc, with no other points. Its convex hull has all the points on the arc as vertices. Now insert one more point, the apex of the triangle. The new convex hull has only three vertices, the vertices of the triangle. —David Eppstein (talk) 17:21, 8 April 2021 (UTC)