A LIBRARY FOR DOING POLYHEDRAL OPERATIONS
作者:
DORANK. WILDE,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 2000)
卷期:
Volume 15,
issue 3-4
页码: 137-166
ISSN:1063-7192
年代: 2000
DOI:10.1080/01495730008947354
出版商: Taylor & Francis Group
关键词: Polyhedron;Computational geometry;Double description method;Intersection;Union;Duality;Convex hull;Mixed linear system;F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumeri-cal Algorithms and Problems-Geometrical problems and computations;G.2.m
数据来源: Taylor
摘要:
The design and implementation of a library of C-code procedures to perform operations on rational polyhedra is described. The library supports intersection, union, difference, simplification in context, convex hull, affine image, affine preimage, and computation of dual forms. Since not all of these functions are closed over polyhedra, the library is extended to operate on finite unions of polyhedra. The major design decisions made during the implementation of the library are discussed. The data structure used for representing finite unions of polyhedra is developed and validity rules for the representation of polyhedra are derived. And finally, the algorithms used to implement the various functions in the library are presented.
点击下载:
PDF (713KB)
返 回