𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An optimal real time algorithm for determine the convex hull of a set of points in a plane

✍ Scribed by Z.Q. Wang; L.J. Xiao

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
282 KB
Volume
35
Category
Article
ISSN
0360-8352

No coin nor oath required. For personal study only.

✦ Synopsis

Based on the properties of star polygon and that the convex polygon is a special kind of star polygon, with the star point as the origin and the two lines respectively parallel to the x-axis and y-axis as coordinate axis, a relative coordinate system is built and the planar area is divided into four areas. Based on the new equation of relationship of point to orientation line, inner points and externals point of polygon are quickly separated, the embraced vertices (tangent vertices) of external points are rapidly found. An optimal real time algorithm for constructing the convex hull of a set of points in a plane is proposed.

πŸ“œ SIMILAR VOLUMES

An Optimal Algorithm for the Intersectio
An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
✍ Shreesh Jadhav; Asish Mukhopadhyay; Binay Bhattacharya πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 224 KB

The intersection radius of a finite collection of geometrical objects in the plane is the radius of the smallest closed disk that intersects all the objects in the collection. Bhattacharya et al. showed how the intersection radius can be found in linear time for a collection of line segments in the