Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









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, Abstract, ©

Note:


(LaTeX) Abstract:

Controlled Perturbation (CP, for short) is an approach to implement
efcient 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},
}


Entry last modified by Michael Sagraloff, 03/27/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Michael Sagraloff
Created
03/27/2009 10:38:05 AM
Revision
0.



Editor
Michael Sagraloff



Edit Date
03/27/2009 10:38:05 AM



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section