TY - JOUR

T1 - Computing the width of a three-dimensional point set

T2 - An experimental study

AU - Schwerdt, Jörg

AU - Smid, Michiel

AU - Majhi, Jayanth

AU - Janardan, Ravi

PY - 1999/12/31

Y1 - 1999/12/31

N2 - 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. Categories and Subject Descriptors: F.2.2 [Nonnumerical Algorithms and Problems]: Geometrical problems and computations; J.6 [Computer-Aided Engineering]: Computer-aided manufacturing (CAM).

AB - 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. Categories and Subject Descriptors: F.2.2 [Nonnumerical Algorithms and Problems]: Geometrical problems and computations; J.6 [Computer-Aided Engineering]: Computer-aided manufacturing (CAM).

KW - Computational Geometry

KW - Implementation

KW - Layered Manufacturing

KW - spherical geometry

UR - http://www.scopus.com/inward/record.url?scp=84871100865&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84871100865&partnerID=8YFLogxK

U2 - 10.1145/347792.347816

DO - 10.1145/347792.347816

M3 - Article

AN - SCOPUS:84871100865

SN - 1084-6654

VL - 4

SP - 8

JO - ACM Journal of Experimental Algorithmics

JF - ACM Journal of Experimental Algorithmics

ER -