# Ascertain properties of a new kind of rectilinear-convex set

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.

• Could you provide a stand-alone definition (no comments) of a rectilinear line segment in a comment below mine? – Włodzimierz Holsztyński Sep 29 '16 at 19:17

This problem is closely related to the problem of finding the shortest multipath connecting $n$ points:
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.