Portal de Periódicos da CAPES

On the definition and computation of rectilinear convex hulls

1984; Elsevier BV; Volume: 33; Issue: 3 Linguagem: Inglês

10.1016/0020-0255(84)90025-2

1872-6291

Thomas Ottmann, Eljas Soisalon-Soininen, Derick Wood,

Optimization and Packing Problems

Recently the computation of the rectilinear convex hull of a collection of rectilinear polygons has been studied by a number of authors. From these studies three distinct definitions of rectilinear convex hulls have emerged. We examine these three definitions for point sets in general, pointing out some of their consequences, and we give optimal algorithms to compute the corresponding rectilinear convex hulls of a finite set of points in the plane.