Share Email Print

Proceedings Paper

Constructing the convex hull of a planar density-bounded integral-points set in linear time
Author(s): Junhui Deng; Zesheng Tang; Meihe Xu
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

A special kind of points sets named DPDIS is defined in this paper, followed by an elegant algorithm for constructing the convex hull of this class of points sets. Taking advantages of the characteristics of this sets category, this algorithm finishes its work within an O(N) complexity. The crux of this algorithm is a new sorting method by which all points can be sorted along x direction in linear time.

Paper Details

Date Published: 22 March 1996
PDF: 5 pages
Proc. SPIE 2644, Fourth International Conference on Computer-Aided Design and Computer Graphics, (22 March 1996); doi: 10.1117/12.235538
Show Author Affiliations
Junhui Deng, Tsinghua Univ. (China)
Zesheng Tang, Tsinghua Univ. (China)
Meihe Xu, Tsinghua Univ. (China)

Published in SPIE Proceedings Vol. 2644:
Fourth International Conference on Computer-Aided Design and Computer Graphics
Shuzi Yang; Ji Zhou; Cheng-Gang Li, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?