Article ID Journal Published Year Pages File Type
6868513 Computational Geometry 2018 15 Pages PDF
Abstract
We study the Oβ-hull of a planar point set, a generalization of the Orthogonal Convex Hull where the coordinate axes form an angle β. Given a set P of n points in the plane, we show how to maintain the Oβ-hull of P while β runs from 0 to π in Θ(nlog⁡n) time and O(n) space. With the same complexity, we also find the values of β that maximize the area and the perimeter of the Oβ-hull and, furthermore, we find the value of β achieving the best fitting of the point set P with a two-joint chain of alternate interior angle β.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,