Reliable and Efficient Computational Geometry Via Controlled Perturbation

Ontology type: schema:Chapter

Chapter Info

DATE

2006

AUTHORS ABSTRACT

Most algorithms of computational geometry are designed for the Real-RAM and non-degenerate input. We call such algorithms idealistic. Executing an idealistic algorithm with floating point arithmetic may fail. Controlled perturbation replaces an input x by a random nearby \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{x}$\end{document} in the δ-neighborhood of x and then runs the floating point version of the idealistic algorithm on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{x}$\end{document}. The hope is that this will produce the correct result for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{x}$\end{document} with constant probability provided that δ is small and the precision L of the floating point system is large enough. We turn this hope into a theorem for a large class of geometric algorithms and describe a general methodology for deriving a relation between δ and L. We exemplify the usefulness of the methodology by examples. More... »

PAGES

299-310

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-35904-3
978-3-540-35905-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11786986_27

DOI

http://dx.doi.org/10.1007/11786986_27

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1002414006

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, 66123, Saarbr\u00fccken, Germany",
"id": "http://www.grid.ac/institutes/grid.419528.3",
"name": [
"Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, 66123, Saarbr\u00fccken, Germany"
],
"type": "Organization"
},
"familyName": "Mehlhorn",
"givenName": "Kurt",
"id": "sg:person.011757371347.43",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, 66123, Saarbr\u00fccken, Germany",
"id": "http://www.grid.ac/institutes/grid.419528.3",
"name": [
"Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, 66123, Saarbr\u00fccken, Germany"
],
"type": "Organization"
},
"familyName": "Osbild",
"givenName": "Ralf",
"id": "sg:person.016215412232.58",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016215412232.58"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, 66123, Saarbr\u00fccken, Germany",
"id": "http://www.grid.ac/institutes/grid.419528.3",
"name": [
"Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, 66123, Saarbr\u00fccken, Germany"
],
"type": "Organization"
},
"familyName": "Sagraloff",
"givenName": "Michael",
"id": "sg:person.012604035513.60",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012604035513.60"
],
"type": "Person"
}
],
"datePublished": "2006",
"datePublishedReg": "2006-01-01",
"description": "Most algorithms of computational geometry are designed for the Real-RAM and non-degenerate input. We call such algorithms idealistic. Executing an idealistic algorithm with floating point arithmetic may fail. Controlled perturbation replaces an input x by a random nearby \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{x}$\\end{document} in the \u03b4-neighborhood of x and then runs the floating point version of the idealistic algorithm on \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{x}$\\end{document}. The hope is that this will produce the correct result for \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{x}$\\end{document} with constant probability provided that \u03b4 is small and the precision L of the floating point system is large enough. We turn this hope into a theorem for a large class of geometric algorithms and describe a general methodology for deriving a relation between \u03b4 and L. We exemplify the usefulness of the methodology by examples.",
"editor": [
{
"familyName": "Bugliesi",
"givenName": "Michele",
"type": "Person"
},
{
"familyName": "Preneel",
"givenName": "Bart",
"type": "Person"
},
{
"familyName": "Sassone",
"type": "Person"
},
{
"familyName": "Wegener",
"givenName": "Ingo",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/11786986_27",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-35904-3",
"978-3-540-35905-0"
],
"name": "Automata, Languages and Programming",
"type": "Book"
},
"keywords": [
"non-degenerate inputs",
"computational geometry",
"geometric algorithms",
"real RAM",
"large class",
"constant probability",
"\u03b4-neighborhood",
"such algorithms",
"general methodology",
"point version",
"most algorithms",
"input x",
"algorithm",
"correct results",
"perturbations",
"theorem",
"point system",
"geometry",
"probability",
"methodology",
"class",
"version",
"point",
"input",
"system",
"vias",
"results",
"relation",
"usefulness",
"hope",
"example"
],
"name": "Reliable and Efficient Computational Geometry Via Controlled Perturbation",
"pagination": "299-310",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1002414006"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/11786986_27"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/11786986_27",
"https://app.dimensions.ai/details/publication/pub.1002414006"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-12-01T06:47",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_173.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/11786986_27"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11786986_27'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11786986_27'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11786986_27'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11786986_27'

This table displays all metadata directly associated to this object as RDF triples.

119 TRIPLES      22 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author Ncce16a1ec84d40d9b143868c11e4c577
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description Most algorithms of computational geometry are designed for the Real-RAM and non-degenerate input. We call such algorithms idealistic. Executing an idealistic algorithm with floating point arithmetic may fail. Controlled perturbation replaces an input x by a random nearby \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{x}$\end{document} in the δ-neighborhood of x and then runs the floating point version of the idealistic algorithm on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{x}$\end{document}. The hope is that this will produce the correct result for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{x}$\end{document} with constant probability provided that δ is small and the precision L of the floating point system is large enough. We turn this hope into a theorem for a large class of geometric algorithms and describe a general methodology for deriving a relation between δ and L. We exemplify the usefulness of the methodology by examples.
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N68d37bfc0b674a769ff1d1cd8b20c1f6
11 schema:keywords algorithm
12 class
13 computational geometry
14 constant probability
15 correct results
16 example
17 general methodology
18 geometric algorithms
19 geometry
20 hope
21 input
22 input x
23 large class
24 methodology
25 most algorithms
26 non-degenerate inputs
27 perturbations
28 point
29 point system
30 point version
31 probability
32 real RAM
33 relation
34 results
35 such algorithms
36 system
37 theorem
38 usefulness
39 version
40 vias
41 δ-neighborhood
42 schema:name Reliable and Efficient Computational Geometry Via Controlled Perturbation
43 schema:pagination 299-310
44 schema:productId N28b284e7805a4520904d7876d9239dc2
45 N31c8a9a8c270444b8f1f198a2b6ba880
46 schema:publisher Ncc138babbdef49498b26a41e5de16bab
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002414006
48 https://doi.org/10.1007/11786986_27
49 schema:sdDatePublished 2022-12-01T06:47
51 schema:sdPublisher N4f292e10dc5342519cded785326491f8
52 schema:url https://doi.org/10.1007/11786986_27
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N07d1f5657fd4464da4dfe3e400aac96b schema:familyName Sassone
58 rdf:type schema:Person
59 N1341e147b3a64c8e98ba4165efb3e394 rdf:first sg:person.016215412232.58
60 rdf:rest N8fd8f411bf7b4496a09aa0a241584261
61 N169e5d4df1a64468b1f05586edc19fbb rdf:first Na71dd4d683564d09aaa6ba7b815b6a10
62 rdf:rest Nd73884d3fcfc49f09b4b6a5e8b5b3701
63 N28b284e7805a4520904d7876d9239dc2 schema:name doi
64 schema:value 10.1007/11786986_27
65 rdf:type schema:PropertyValue
66 N31c8a9a8c270444b8f1f198a2b6ba880 schema:name dimensions_id
67 schema:value pub.1002414006
68 rdf:type schema:PropertyValue
69 N4f292e10dc5342519cded785326491f8 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N68d37bfc0b674a769ff1d1cd8b20c1f6 schema:isbn 978-3-540-35904-3
72 978-3-540-35905-0
73 schema:name Automata, Languages and Programming
74 rdf:type schema:Book
75 N8fd8f411bf7b4496a09aa0a241584261 rdf:first sg:person.012604035513.60
76 rdf:rest rdf:nil
77 N9490ca92a2774e138e153d48a566874f schema:familyName Bugliesi
78 schema:givenName Michele
79 rdf:type schema:Person
80 Na71dd4d683564d09aaa6ba7b815b6a10 schema:familyName Preneel
81 schema:givenName Bart
82 rdf:type schema:Person
84 rdf:rest N169e5d4df1a64468b1f05586edc19fbb
85 Ncc138babbdef49498b26a41e5de16bab schema:name Springer Nature
86 rdf:type schema:Organisation
87 Ncce16a1ec84d40d9b143868c11e4c577 rdf:first sg:person.011757371347.43
88 rdf:rest N1341e147b3a64c8e98ba4165efb3e394
89 Ncfb3497ffc424576920b3d7e89f2455a schema:familyName Wegener
90 schema:givenName Ingo
91 rdf:type schema:Person
92 Nd60d508261684983a58daf9d0c506ed7 rdf:first Ncfb3497ffc424576920b3d7e89f2455a
93 rdf:rest rdf:nil
94 Nd73884d3fcfc49f09b4b6a5e8b5b3701 rdf:first N07d1f5657fd4464da4dfe3e400aac96b
95 rdf:rest Nd60d508261684983a58daf9d0c506ed7
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
100 schema:name Computation Theory and Mathematics
101 rdf:type schema:DefinedTerm
102 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
103 schema:familyName Mehlhorn
104 schema:givenName Kurt
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
106 rdf:type schema:Person
107 sg:person.012604035513.60 schema:affiliation grid-institutes:grid.419528.3
108 schema:familyName Sagraloff
109 schema:givenName Michael
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012604035513.60
111 rdf:type schema:Person
112 sg:person.016215412232.58 schema:affiliation grid-institutes:grid.419528.3
113 schema:familyName Osbild
114 schema:givenName Ralf
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016215412232.58
116 rdf:type schema:Person
117 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123, Saarbrücken, Germany
118 schema:name Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123, Saarbrücken, Germany
119 rdf:type schema:Organization