Abstract | ||
---|---|---|
This paper presents an alternate choice of computing the convex hulls (CHs) for planar point sets. We firstly discard the interior points and then sort the remaining vertices by x-/y- coordinates separately, and later create a group of quadrilaterals (e-Quads) recursively according to the sequences of the sorted lists of points. Finally, the desired CH is built based on a simple polygon derived from all e-Quads. Besides the preprocessing for original planar point sets, this algorithm has another mechanism of discarding interior point when form e-Quads and assemble the simple polygon. Compared with three popular CH algorithms, the proposed algorithm can generate CHs faster than the three but has a penalty in space cost. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/ICCSNT.2012.6526070 | Computer Science and Network Technology |
Keywords | Field | DocType |
e-quads,extreme points,computational geometry,set theory,planar point sets,point set,convex hulls,simple polygon,convex hull,quadrilaterals | Combinatorics,Convex geometry,Convex combination,Convex hull,Algorithm,Krein–Milman theorem,Convex set,Regular polygon,Simple polygon,Interior point method,Mathematics | Journal |
Volume | ISSN | ISBN |
abs/1212.6043 | 2012 2nd International Conference on , vol., no., pp.888,891,
29-31 Dec. 2012 | 978-1-4673-2963-7 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gang Mei | 1 | 23 | 6.98 |
John C. Tipper | 2 | 6 | 3.90 |
Nengxiong Xu | 3 | 22 | 6.00 |