Reliable and Efficient Computational Geometry Via Controlled Perturbation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Kurt Mehlhorn , Ralf Osbild , Michael Sagraloff

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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "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", 
        "givenName": "Vladimiro", 
        "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-10-01T06:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_221.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11786986_27"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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'

Turtle is a human-readable linked data format.

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
1 sg:pub.10.1007/11786986_27 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N62c786355baa4304a60163241fa01003
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.
7 schema:editor N309ead9d23e14b04a6bce2f8f3c48ca5
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N335eab08510f4eb683b741c7eddd1d55
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 N4f959922637b4593ad4d29dcf28fa395
45 N8160455b5acb44bb978606875c06df4d
46 schema:publisher N8eb280d6f586442ebef04f6bae16d086
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002414006
48 https://doi.org/10.1007/11786986_27
49 schema:sdDatePublished 2022-10-01T06:54
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Nf9514a1bb578481d8f2ff5d2844cc868
52 schema:url https://doi.org/10.1007/11786986_27
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N07445680391644958334bf92f4b610eb schema:familyName Sassone
57 schema:givenName Vladimiro
58 rdf:type schema:Person
59 N309ead9d23e14b04a6bce2f8f3c48ca5 rdf:first Nc2ed6622af8e45828abf311df0c4d293
60 rdf:rest Nf26b351b06a74cc8bcaa2653b429b112
61 N335eab08510f4eb683b741c7eddd1d55 schema:isbn 978-3-540-35904-3
62 978-3-540-35905-0
63 schema:name Automata, Languages and Programming
64 rdf:type schema:Book
65 N4f959922637b4593ad4d29dcf28fa395 schema:name doi
66 schema:value 10.1007/11786986_27
67 rdf:type schema:PropertyValue
68 N62c786355baa4304a60163241fa01003 rdf:first sg:person.011757371347.43
69 rdf:rest Nd0ed5618573a46898905e4b264f02f8a
70 N7fe03e98b26a4cc6bc74f2f0535d9a52 schema:familyName Wegener
71 schema:givenName Ingo
72 rdf:type schema:Person
73 N80851e7d37a2418ca65ebbf64b66dbd4 rdf:first N07445680391644958334bf92f4b610eb
74 rdf:rest Ne66abe2df0dd4b2d8cb254ddb27c8e32
75 N80b803278f344af2917c463ad7946bb3 rdf:first sg:person.012604035513.60
76 rdf:rest rdf:nil
77 N8160455b5acb44bb978606875c06df4d schema:name dimensions_id
78 schema:value pub.1002414006
79 rdf:type schema:PropertyValue
80 N8eb280d6f586442ebef04f6bae16d086 schema:name Springer Nature
81 rdf:type schema:Organisation
82 Nc2ed6622af8e45828abf311df0c4d293 schema:familyName Bugliesi
83 schema:givenName Michele
84 rdf:type schema:Person
85 Nd0ed5618573a46898905e4b264f02f8a rdf:first sg:person.016215412232.58
86 rdf:rest N80b803278f344af2917c463ad7946bb3
87 Ne66abe2df0dd4b2d8cb254ddb27c8e32 rdf:first N7fe03e98b26a4cc6bc74f2f0535d9a52
88 rdf:rest rdf:nil
89 Nf26b351b06a74cc8bcaa2653b429b112 rdf:first Nf8d55a4ccef14fef8922719839b435ea
90 rdf:rest N80851e7d37a2418ca65ebbf64b66dbd4
91 Nf8d55a4ccef14fef8922719839b435ea schema:familyName Preneel
92 schema:givenName Bart
93 rdf:type schema:Person
94 Nf9514a1bb578481d8f2ff5d2844cc868 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
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
 




Preview window. Press ESC to close (or click here)


...