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)

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)

This inconsistency was noticed and studied by Ottman et al. . 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).--Carlos Alegría (talk) 21:31, 12 August 2011 (UTC)

Actually from what you say it sounds like the one we are using is the classical one, not the connected one. —David Eppstein (talk) 22:59, 12 August 2011 (UTC)

From the second paragraph of the article: "The orthogonal convex hull of a set $S\subset \mathbb {R} ^{n}$ is the intersection of all connected orthogonally convex supersets of S". That's exactly the definition of the connected rectilinear convex hull stated by Ottman et al. The definition of the traditional convex hull that I talked about is the following: The convex hull of a point set $P$ is the intersection of all convex supersets of $P$. Which is exactly the one used in the first version of the article.--Carlos Alegría (talk) 12:18, 13 August 2011 (UTC)

Then I'm confused by what you mean about non-uniqueness. "The intersection of all connected orthogonally convex supersets" is uniquely defined, though not necessarily itself connected. —David Eppstein (talk) 03:54, 14 August 2011 (UTC)

You're right, by reading more carefully Karlsson–Overmars et al. and Ottman et al. I realized I made a mistake. Just to be cristal clear, this are the definitions that can be found in the literature (according to Ottman et al.):

• Classical: The rectilinear convex hull, or r-convex hull, of a point set $P$ is the smallest rectilinearly convex (r-convex) supersets of $P$. Clearly, this is equivalent to say that the r-convex hull is the intersection of all r-convex sets containing $P$. The r-convex hull is uniqueliy defined and might be disconnected.
• Connected: The connected r-convex hull, or cr-convex hull, of a point set $P$ is the smallest connected r-convex set containing $P$. The cr-convex hull is always connected but is not uniquely defined (i.e. there are several cr-convex hulls for the same point set).
• Maximal: The maximal r-convex hull, or mr-convex hull, of a point set $P$ is the intersection of all cr-convex set containing $P$. This is equivalent to say that the mr-convex hull is the intersection of all closed rectilinear half planes containing $P$. The mr-convex hull is uniquely defined and might be disconnected. Ottman et al. named it maximal because it is related to the vectorial domination relation studied by Preparata et al..

Notice that by considering the intersection and the smallest cr-convex supersets of $P$ we obtain different convex hulls (I think that's why I got confused). Notice also that strictly speaking, in Karlsson–Overmars et al. they use the classical definition but actually they compute the mr-convex hull. I think that they weren't that strict with those details, as the vertex set of both hulls is the same.--Carlos Alegría (talk) 20:48, 14 August 2011 (UTC)

Ok, in "teach the controversy" mode, I think we should include all three definitions with some discussion about how they differ and about which sources use which definition rather than trying to choose one ourselves here. I think also that the "connected" one is the one that is closest to the tight span — I think all connected hulls are isometric to each other and to the tight span though not necessarily congruent to each other — but that may be difficult to find an appropriate citation for, because the tight span theory literature and the orthogonal convex hull literature are not very well coupled to each other. —David Eppstein (talk) 02:33, 15 August 2011 (UTC)

I added a new section here to discuss the article's modifications.--Carlos Alegría (talk) 12:57, 19 August 2011 (UTC)

I added a new section to the article describing these three definitions, along with some pictures and descriptions of their basic properties.--Carlos Alegría (talk) 20:24, 9 May 2020 (UTC)

Restructuring

I did the following to start article's improvement:

• Added a template at the top of the article to indicate that it is under major modifications.
• Made a copy of the article on my sandbox to start the edition. In this version I added another reference that I found when researching for my thesis, in which the authors also define and study the rectilinear convex hull using different notation.
• Added the article to the WikiProject Computer Science, as I think the content is relevant for this project.

This is my first time editing an article. I read Wikipedia's article edition documentation, but I still think that I might be making mistakes on the appropiate way to do this. Specifically, I am not sure about which one is the suitable template to indicate a major modification of an existing article.--Carlos Alegría (talk) 16:37, 18 August 2011 (UTC)

References

The following references are not included in the article. I added them here for the discussion clarity's sake.--Ccristoo (talk) 20:49, 14 August 2011 (UTC)

degeneracy

So I guess the OCH of {(0,0), (1,1)} is empty? —Tamfang (talk) 22:14, 27 January 2015 (UTC)

Not empty, but it just consists of those two isolated points. —David Eppstein (talk) 22:27, 27 January 2015 (UTC)