-1
$\begingroup$

Edit : Consider giving a reason for down vote.

In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-Rectilinear Convex Hull (or mr-convex hull) is given on page 160, Def 2.4 of the linked paper. In the attached image I have tried to explain my problem. Please read the image in the numeric sequence of 1 to 4 to understand my question.

image,

Appreciate any help in clearing my confusion.

Improve this question
$\endgroup$
5
  • $\begingroup$ What is the reason for down vote? I am new to both Maths and Maths-Overflow. Would appreciate reasons for down voting as well. $\endgroup$
    – Abhinav
    Commented Sep 24, 2015 at 20:57
  • $\begingroup$ I haven't voted on your question but I find it very hard to figure out exactly what you are asking. I suspect I am not the only one. Some advice which may be useful to you as a new member can be found here meta.mathoverflow.net/questions/882/… $\endgroup$
    – j.c.
    Commented Sep 24, 2015 at 21:39
  • $\begingroup$ I just checked. The paper link was broken. Apart from that, I don't see what is wrong with the question. >>The question is precise. >>I have quoted a definition from a journal paper and I have given the link to it as well. >> I have tried to make a sketch explaining my dilemma instead of trying to keep it in words. I don't know what else shall I do. $\endgroup$
    – Abhinav
    Commented Sep 24, 2015 at 22:29
  • 4
    $\begingroup$ I think this is a better fit for math.stackexchange. (Mathematically, the definition is elementary, so this question isn't really suitable for this specific site, even though it is a good question.) $\endgroup$
    – Noah Schweber
    Commented Sep 24, 2015 at 22:52
  • $\begingroup$ @NoahSchweber appreciate the direction. $\endgroup$
    – Abhinav
    Commented Sep 24, 2015 at 22:56

2 Answers 2

Reset to default
4
$\begingroup$

This is a confusing concept, as acknowledged in the paper you cite, "On the definition and computation of rectilinear convex hulls" (Elsevier link).

          WikiImage
          (Image from Wikipedia.)
It may help to look at this more modern paper:

Alegría-Galicia, Carlos, Tzolkin Garduño, Areli Rosas-Navarrete, Carlos Seara, and Jorge Urrutia. "Rectilinear convex hull with minimum area." In Computational Geometry, pp. 226-235. Springer Berlin Heidelberg, 2012. (PDF download.)

Excerpt from A-G et al.:

  OrthoHull

Improve this answer
$\endgroup$
4
  • $\begingroup$ A-G et al. paper says on its second page : " Throughout this paper, we will use the maximal ortho-convex , or mr-convex hull stated by Ottmann et al." But the paper goes on giving definition of Rectilinear Convex Hull as [R-Hull of Point Set P] = [R^{2} - Union(Quadrants Free of Point Set)]. Does it mean, the algorithm discussed in Ottmann et. al. and A-G et al. gives the mr-convex hull of a point set and not the r-convex hull of the point set? Because using the definition of A-G et al., for three non-collinear points, I can only get the mr-convex hull and not the r-convex hull of the points. $\endgroup$
    – Abhinav
    Commented Sep 24, 2015 at 23:40
  • $\begingroup$ @Abhinav: I don't see your confusion. They (A-G et al.) define "The 'Rectilinear Convex Hull' of P with orientation θ [as] the set" etc. And the remainder of their paper seems clear. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 24, 2015 at 23:42
  • $\begingroup$ Consider the two definitions. (1) Defn 2.4 in Ottmann et. al. of mr-convex hull (2) Defn of Rectilinear Convex Hull with fixed orientation given in A-G et al. which can be seen HERE Hence, for my example of 3 non-collinear points, both the definitions shall give the mr-convex hull. Because the r-convex hull of three non-collinear points can only be the three points themselves. So my confusion is : Is A-G et al. talking about r-convex hull but actually their algo gives mr-convex hull. Am I right? $\endgroup$
    – Abhinav
    Commented Sep 25, 2015 at 0:06
  • 1
    $\begingroup$ >"their algo gives mr-convex hull.": I think your interpretation is correct. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 25, 2015 at 0:40
1
$\begingroup$

After understanding the logic of creating mr-convex hull of a set of points, I tried making a sketch that explains the idea clearly (hopefully) for a point set of 3 non-collinear points. You can access the sketch here. I have used the definition of mr-convex hull shown here taken from this paper.

Also, I think the two important papers in this field, paper-1 and paper-2 are confusing on one aspect. Both papers read that the algo they present are for obtaining the r-convex hull and then cr-convex hull (from the obtained r-convex hull) of a set of points. Whereas, I think both the papers' algo compute the mr-convex hull first and then the cr-convex hull (from the mr-convex hull).

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .