Talk:Orthogonal convex hull

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)[reply]

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)[reply]

This inconsistency was noticed and studied by Ottman et al. (http://www.sciencedirect.com/science/article/pii/0020025584900252). They presented three definitions for the rectilinear convex hull of a planar point set. The one used here is called the connected rectilinear convex hull, which has the "flaw" of not be unique for a given point set. The classical version is the same one of the traditional convex hull. For ortho-convexity, this definition leads to a disconnected set. The last one is called the maximal rectilinear convex hull. Although it also leads to a disconnected set, it has found applications in several fields. I think that it is appropiate to add the three definitions here (I probably will when I have some time).--Ccristoo (talk) 21:31, 12 August 2011 (UTC)[reply]