Optimal computation of finitely oriented convex hulls

DOI10.1016/0890-5401(87)90045-9MaRDI QIDQ1820432zbMATH OpenOpenAlexFDO

Authors Gregory J. E. Rawlins, D. Wood

Publication date 1987

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(87)90045-9

zbMATH Keywords

convex hullF-convexityoptimal algorithms

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Polytopes and polyhedra (52Bxx) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• Finding the convex hull of a simple polygon
• The convex hull of a set of convex polygons
• scientific article; zbMATH DE number 4045150
• On finding the convex hull of a simple polygon
• Finding the convex hull of a simple polygon in linear time

Cites work

• A linear algorithm for finding the convex hull of a simple polygon
• A new linear convex hull algorithm for simple polygons (Corresp.)
• Dynamic C-oriented polygonal intersection searching
• Finding the convex hull of a simple polygon
• scientific article; zbMATH DE number 3911725 (Why is no real title available?)
• scientific article; zbMATH DE number 3995096 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• scientific article; zbMATH DE number 3290019 (Why is no real title available?)
• On finding the convex hull of a simple polygon
• On the definition and computation of rectilinear convex hulls
• On the identification of the convex hull of a finite set of points in the plane
• On the X-Y convex hull of a set of X-Y polygons

Cited in

(23)

• Partitioning and separating sets of orthogonal polygons
• Restricted-oriented convex sets
• Fast linear expected-time algorithms for computing maxima and convex hulls
• Generalized halfspaces in restricted-orientation convexity
• Computing minimum length paths of a given homotopy class
• Fundamentals of restricted-orientation convexity
• Oracle-polynomial-time approximation of largest simplices in convex bodies
• On the \(\mathcal{O}_\beta\)-hull of a planar point set
• A decompositin theorem for convexity spaces
• Staircase visibility and computation of kernels
• Computing min-convex hulls in the affine building of \(\mathrm{SL}_d\)
• Minimum-link paths revisited
• Angle-restricted tours in the plane.
• Efficient Computation of the Outer Hull of a Discrete Path
• scientific article; zbMATH DE number 5302815 (Why is no real title available?)
• Method of orienting curves for determining the convex hull of a finite set of points in the plane
• scientific article; zbMATH DE number 4062042 (Why is no real title available?)
• scientific article; zbMATH DE number 6846375 (Why is no real title available?)
• PLANAR STRONG VISIBILITY
• Efficient edge-skeleton computation for polytopes defined by oracles
• Shortcut hulls: vertex-restricted outer simplifications of polygons
• Dominance for enclosure problems
• The intersection searching problem for c-oriented polygons

This page was built for publication: Optimal computation of finitely oriented convex hulls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820432)