Knowledge Base

Home  Search   Show all  Top

Details of the record

titleA complete implementation for computing general dimensional convex hulls
authorsJoannis z. Emiris
keywordsconvex hull, general dimension, beneath-beyond algorithm, modular arithmetic, randomization, infinitesimal perturbation, postprocessing robustness
abstractWe study two important, and often complementary, issues in the implementation of geometric algorithms, namely exact arithmetic and degeneracy. We focus on integer arithmetic
and propose a general and efficient method for its implementation based on modular arithmetic. We suggest that probabilistic modular arithmetic may be of wide interest, as it combines the advantages of modular arithmetic with randomization in order to speed up the lifting of residues to
an integer. We derive general error bounds and discuss the implementation of this approach in our general-dimension convex hull program. The use of perturbations as a method to cope with input degeneracy is also illustrated. We present the implementation of a computationally efficient
scheme that, moreover, greatly simplifies the task of programming. We concentrate on postprocessing, often perceived as the Achilles' heel of perturbations. Starting in the context of a specific application in robotics, we examine the complexity of postprocessing and attempt to delimit the
cases where perturbations become a hindrance rather than an enhancement. Lastly, we discuss the visualization capabilities of our software and illustrate them for problems in computational algebraic geometry.
journalInternational journal of computational geometry & applications
published year
(Total records:1429)
Home  Search   Show all  Top

Powered by: DaDaBIK