دانلود کتاب هندسه محاسباتی با عدم قطعیت های مستقل و وابسته

Geometric uncertainty is ubiquitous in mechanical CAD/CAM, robotics, computer vision, wireless networks and many other fields. Sensing, localization, measurement and manufacturing processes are intrinsically imprecise, and thereby introduce error and uncertainty. In contrast, the corresponding geometric models are usually exact and do not account for these inaccuracies. Modeling and computing geometric variability and its consequences are thus of great scientific, technical and economic importance. This book presents LPGUM (Linear Parametric Geometric Uncertainty Model), a parametric model for representing geometric entities with dependent uncertainties between them. LPGUM allows the systematic study of geometric uncertainty and its related algo- rithms. In this model, basic geometric features, such as coordinates, points, lines and arcs, are defined by a common set of parameters with uncertainty intervals. The uncertainty zones around nominal feature locations are defined by uncertainty sensitivity matrices whose entries indicate the coordinates’ sensitivity to parameter variations and their dependencies. The sensitivity matrices are derived from the functional relations between the design or measurement parameters by taking the partial derivative of the function for each parameter at the nominal value. The sensitivity matrices allow modeling of the full range of uncertainty dependency and parameter coupling, from independence through partial dependency, to complete dependency. The book formalizes the concept of geometric uncertainty with dependencies and presents efficient algorithms to solve four key problems: (1) compute the envelope of uncertain lines and circles; (2) answer geometric half-plane retrieval queries of points in the plane, including exact and uncertain point sets and half-plane queries defined by an exact or uncertain line; (3) construct the Euclidean Minimum Spanning Tree (EMST) of a set of uncertain points, test its stability and compute its total weight; (4) construct the Voronoi diagram (VD) and Delaunay triangulation (DT) of a set of uncertain points, test their stability, compute their components, answer exact and uncertain point location queries in a stable uncertain VD and dynamically update it. The main contribution of this book is the model which allows for describing and efficiently handling geometric objects with depen- dent uncertainty. We show that the model is expressive and that the additional computational cost for allowing for dependent uncer- tainty using this model is in most cases a low polynomial multiplica- tive term