Technical, Research Report @TechReport Technischer-, Forschungsbericht

 Show entries of: this year (2021) | last year (2020) | two years ago (2019) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Mehlhorn, Kurt Osbild, Ralf Sagraloff, Michael dblp dblp dblp
 Editor(s):
 BibTeX Citekey*: ACS-TR-361502-02 Language: English

 Title, Institution
 Title*: A General Approach to the Analysis of Controlled Perturbation Algorithms Institution*: University of Groningen Publishers or Institutions Address*: 9700 AB Groningen THE NETHERLANDS Type: Technical Report

 No, Year, pp.,
 Number*: ACS-TR-361502-02 Pages*: 24 Month: VG Wort Pages*: 361502-02 Year*: 2008 ISBN/ISSN: DOI:

 Note: (LaTeX) Abstract: Controlled Perturbation (CP, for short) is an approach to implement efcient and robust geometric algorithms using the computational speed of builtin nite precision arithmetic, while bypassing precision problems during the computation. Furthermore it avoids the time-consuming and error-prone discussion of degenerate cases. CP replaces the input objects by a set of randomly perturbed (moved, scaled, stretched, etc.) objects such that the algorithm is guaranteed to compute the exact combinatorial structure that these objects imply. This paper is meant as a guide how to decide if CP can be applied to a given algorithm, and if, how to correlate all CP parameters: the perturbation amount d , the arithmetic precision $L$, the maximum range of input values $[−m,m]$, the number of input objects $n$, the error bound $\mathcal{B}_f$ of the (chosen) predicate evaluations, and the probability $\mathcal{P}$ of a successful computation. For this purpose we present a general methodology to analyze predicate functions that leads to an inequality correlating these parameters and hence to bounds on the precision or perturbation amount. In particular we treat the case of the wide used class of polynomial predicates in detail. Advantages, drawbacks and implementation issues are discussed. Categories / Keywords: Copyright Message: HyperLinks / References / URLs: http://acs.cs.rug.nl/acstr/ACS-TR-361502-02.pdf Personal Comments: File Upload: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group MPG Subsubunit: Geometric Computing Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
@TECHREPORT{ACS-TR-361502-02,
AUTHOR = {Mehlhorn, Kurt and Osbild, Ralf and Sagraloff, Michael},
TITLE = {A General Approach to the Analysis of Controlled Perturbation Algorithms},
YEAR = {2008},
TYPE = {Technical Report},
INSTITUTION = {University of Groningen},
NUMBER = {ACS-TR-361502-02},
PAGES = {24},
ADDRESS = {9700 AB Groningen THE NETHERLANDS},
}