Optimal computation of finitely oriented convex hulls
type: Item
instance of: scholarly article
title: Optimal computation of finitely oriented convex hulls
zbMATH Open document ID: 0615.52001
DOI: 10.1016/0890-5401(87)90045-9
author: Gregory J. E. Rawlins
author: D. Wood
published in: Information and Computation
publication date: 1987-01-01T00:00:00Z
review text: For a simple finitely oriented polygon four versions of the concept ''convex hull'' are defined. The aim of the paper is to give optimal algorithms to find them. Let F be a finite set of orientations and let an F-polygon be a polygon whose edges have only orientations from F. Further call a polygon F-convex if the intersection of the polygon with any F- line (i.e. a line whose orientation stems from F) is either empty or a line segment. Then the authors derive results like the following. If the orientations in F are sorted then testing a simple F-polygon for F- convexity can be achieved in \(\Theta (n+| F|)\) time and \(\Theta\) (n) space, n being the number of edges of \(\Pi\). The authors also prove a result which gives bounds for time and space during which each of the four hulls can be found optimally.
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 52Bxx
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3996517
zbMATH Keywords: convex hull
zbMATH Keywords: optimal algorithms
zbMATH Keywords: F-convexity
MaRDI profile type: Publication
full work available at URL: 0890-5401(87)90045-9
OpenAlex ID: W1966582767
cites work: A new linear convex hull algorithm for simple polygons (Corresp.)
cites work: Q5572045
cites work: Finding the convex hull of a simple polygon
cites work: Q5547252
cites work: Dynamic C-oriented polygonal intersection searching
cites work: On the identification of the convex hull of a finite set of points in the plane
cites work: On finding the convex hull of a simple polygon
cites work: A linear algorithm for finding the convex hull of a simple polygon
cites work: On the X-Y convex hull of a set of X-Y polygons
cites work: On the definition and computation of rectilinear convex hulls
cites work: Q3687731
cites work: Q4721677
description: scientific article; zbMATH DE number 3996517