 | The ACM Journal of Experimental Algorithmics |
Volume 4, Article 8, 1999
Computing the Width of a Three-Dimensional Point
Set: An Experimental Study
by
and
and
and
http://www.jea.acm.org/1999/SchwerdtWidth/
Abstract:
We describe a robust, exact, and efficient implementation of
an algorithm that computes the width of a three-dimensional
point set. The algorithm is based on efficient solutions
to problems that are at the heart of computational geometry:
three-dimensional convex hulls, point location in planar
graphs, and computing intersections between line segments.
The latter two problems have to be solved for planar graphs
and segments on the unit sphere, rather than in the
two-dimensional plane. The implementation is based on
LEDA, and the geometric objects are represented using
exact rational arithmetic.
- Keywords:
Layered Manufacturing, Computational Geometry, Spherical Geometry
- CR Categories:
F.2.2 Nonnumerical Algorithms and Problems: Geometrical Problems and Computations,
J.6 Computer-Aided Engineering: Computer-Aided Manufacturing (CAM)
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
April 1, 1999
|
January 20, 2000
|
February 3, 2000
|
May 10, 2000
|
Last updated and validated May 10, 2000, by editor@jea.acm.org