Ascertain properties of a new kind of rectilinear-convex set

Question

PREABMLE TO MY QUESTION

I am reading about convex sets and hulls in orthogonal/rectilinear spaces. As can be seen in this publication, for a given set of points in $\mathbb{R}^{2}$, there are many kinds of rectilinear convex hulls. For the ease of people reading my question, I am providing the important definitions using an example below. Note that a rectilinear line (or line-segment) is a straight line (or line-segment) oriented parallel to either the x -axis or the y-axis. A rectilinear curve or staircase is a (finite) line consisting of rectilinear line segments. In the example (image), the Subimage(a) shows the point set in $\mathbb{R}^{2}$ for which the various r-convex hulls are plotted.

Definition 1 (Subimage (a)). A point set is called rectilinear convex, or r-convex, if for any two of its points which determine a rectilinear line segment, the line segment lies entirely in the given set. The point set $\mathbf{P}$ is r-convex.

Definition 2 (Subimage (b)). The rectilinear-convex hull or r-convex hull of a point set is the intersection of all r -convex sets that contain the given set. The r-convex hull of a point set is unique.

Definition 3 (Subimage (c)). The maximal r-convex hull or mr-convex hull of a point set is the intersection of all closed-rectilinear-half-planes (refer figure-4 of publication) that contain it. The mr-convex hull of a point set is unique.

Definition 4 (Subimage (d)). The connected r-convex hull or cr-convex hull of a point set is a smallest connected r-convex set containing the given point set. Observe that cr-convex hulls of a point set are not necessarily unique. In Subimage (d), the staircase a − 1 − b and point c are joined with one of the many staircases possible between points 1 and c. As long as the staircase joining a − 1 − b and c is within or on the box 1 − 3 − c − 2 − 1 (shown with dotted lines), the set will remain the smallest r-convex set containing point set P.

The publication also points out (on page-162) that r-convex hull and mr-convex hull of a point are consistent with the Carathéodory's theorem where as cr-convex hulls are not.

MY QUESTION I want to propose one more type of r-convex hull, namely ucr-convex hull. I define it as :

Definition 5 ucr-convex hull is the set obtained from union of all cr-convex hulls. See Subimage (e).

I intuitively feel that the ucr-convex hull has some nice properties such as uniqueness and consistency (wrt Carathéodory's theorem for regular convex sets). BUT I don't know how to methodically go about proving these properties. Any directions?

Edit 1 : I was able to prove that ucr-covex hulls do not adhere to the Caratheodory's theorem. I am looking for answers on Uniqueness property still though.

Edit 2 : After discussions with someone, I understand that the Uniqueness of ucr-convex hull is trivial as long as the number of smallest rectilinear paths between two points can be proven to be a countable. I dont have any background in real analysis or core maths subjects to be able to produce a formal proof to this intuitive concept. Any help would be appreciated.

Answer 1

Regarding some directions for proofs, I suggest you to take a look at the book on Restricted Orientation Convexity. It is a compilation of results from the authors of the paper you are citing, and contains some generalizations to other types of ortho-convexity. In particular, take a look at the strong-orthogonal convexity. It is another type of convexity that results in a unique and connected hull for any point set.

Regarding the uniqueness of your ucr-convex hull, proving that the number of rectilinear paths between two points is countable depends on the particular space you are dealing with. In an euclidean space (a Cartesian space with euclidean metric), there is a non countable number of points inside the bounding rectangle of the two points, and it is not hard to see that you can create at least different path for any point inside the square bounding all the paths. I think it is more easy to prove that there is a unique bounding square per pair of points, and go from there.

Answer 2

This problem is closely related to the problem of finding the shortest multipath connecting $n$ points:

(not that this is the solution) except using rectilinear lines instead.

The condition that the number of paths is countable (there are an uncountable number anyway - consider a rectipath from $0 \to \alpha$ where $\alpha$ is irrational - is to prevent the rectipath becoming a curve, but I personally don't see this as a problem, and I would say that the union of such shortest recti-multi-paths is unique.