Partha Bhowmick: Orthogonal Convex Hull (original) (raw)

Finding the Orthogonal Convex Hull

(A linear-time combinatorial algorithm)

Algorithm

A. Biswas, P. Bhowmick, M. Sarkar, and B. B. Bhattacharya,
A Linear-time Combinatorial Algorithm to Find the Orthogonal Hull of an Object on the Digital Plane, Information Sciences, Vol. 216, pp. 176-195, 2012.

What's it?

The orthogonal convex hull of a digital object S, denoted by OH(S), is the smallest-area orthogonal polygon such that:
(i) each point p∈S lies lies inside OH(S) and
(ii) intersection of OH(S) with any horizontal or vertical line is either empty or exactly one line segment.