Talk:Orthogonal convex hull

From Wikipedia, the free encyclopedia

[edit] Problem with formulations?

So... if S = {(1, 2), (2, -1), (-1, -2), (-2, 1)}, then S would seem to be orthogonally convex according to the first paragraph. But the end of the second paragraph suggests that (0, 0) should belong to the orthogonally convex hull of S. What's the deal? Melchoir 22:31, 10 November 2006 (UTC)

I looked more carefully at Karlsson–Overmars and Nicholl et al, since they were easiest to find after the Fink–Wood papers which didn't really address this question. Karlsson–Overmarks have the same inconsistency that you point out: they define convexity exactly as here, define the convex hull to be the smallest convex region containing the points, but then what they actually compute is the region between four staircases connecting the four extreme points, and they don't even seem to consider the possibility that two of the four staircases might cross. Nicholl et al are much more careful: they define the convex hull to be the smallest orthogonally-convex polygon that has all edges orthogonal and contains all the points, if such a polygon exists. And it turns out that what they mean by the polygon not existing is that the four staircases cross. I changed the definition in the article to be the intersection of all connected orthogonally-convex sets containing the points, which I believe is very similar to what both are actually doing by intersecting staircases, and is always defined but not always itself connected. But I'm a little worried that this version of the definition may be original research. Alternatively we could use one of the descriptions in Nicholl: either the one about the smallest etc, or the shape bounded by the four staircases if they don't cross. I find both to be more ad-hoc and inelegant, though, which is why I prefer the definition as the intersection of all connected orthogonally-convex supersets. —David Eppstein 00:08, 13 November 2006 (UTC)