Rectilinear convex hull I am working on an algorithm, which takes as input as set points contained inside the Rectilinear Convex Hull of some fixed points in 2-dimension. I tried to find an implementation but met with little success. Can someone direct me to a link where such an algorithm is discussed? An algorithm for a convex hull in euclidean space is available in Matlab, Python, Java and many languages but not in Manhattan space.
Since, I am not a mathematician by training, I might be missing some important resources in my search.
EDIT 1 :
Taking cue from Prof. Rourke's reply, I am trying to implement the algorithm to find the Upper cr-convex hull given on Page-167 of the paper here. Can someone explain to me what is meant by "Maximal Monotonic Increasing Sequence" in Step-2 of the algorithm.
 A: Perhaps you cannot find what you seek because there is another phrase used for the same concept, orthogonal convex hull. E.g., there is a Wikipedia article:



Wikipedia image.

Two papers on the topic are cited below:


Ottman, T., Soisalon-Soisinen, E., Wood D.: On the definition and computation
  of rectilinear convex hulls. Information Sciences, 33, 157–171 (1984)
  14. Preparata, F., Shamos, M.I.: Computational Geometry: An Introduction. SpringerVerlag
  (1985). (Journal link.)

Their cr-convex hull definition is likely the best option. It can be computed in
optimal $O(n \log n)$ time.

Rawlins, G.J.E., Wood, D.: Ortho-convexity and its generalizations. Computational
  Morphology: A Computational Geometric Approach to the Analysis of Form,
  137–152. Elseiver Science Publishers B.V., North-Holland (1988).

A: I implemented the algorithm in Java for visualization purposes. You can find it on github. If you find it difficult to extract the actual algorithm from the code, please let me know.
You can also take a look at the $L_\infty$ package of CGAL. The vertices of the outer face of the Delaunay triangulation in the $L_\infty$ metric are the vertices of the Rectilinear Convex Hull. So you can use that library to compute the vertices. It is an overkill, but it is a robust and ready-to-use implementation.
Finally, if want to give it a try, the algorithm is actually not that hard to implement. The vertices of the rectilinear convex hull are the maximal points under vector domination with respect to the four quadrants defined by the coordinate axes. A very easy to follow pseudo code can be found in the book from Preparata.
Preparata, Franco P.; Shamos, Michael Ian, Computational geometry. An introduction, Texts and Monographs in Computer Science. New York etc.: Springer-Verlag. XII, 390 p. DM 148.00 (1985). ZBL0575.68059.
You can find the pseudocode in page 154. You will notice that the book does not mention anything about the rectilinear convex hull, since the connection with the set maxima problem was published later.
