| Property |
Value |
| dbo:abstract
|
- En géométrie algorithmique, l'algorithme de Bentley-Ottmann est un algorithme de sweep line pour trouver les (en). C'est une généralisation de l'algorithme de Shamos et Hoey qui vérifie si un ensemble de segments possède des intersections ou non. Pour n segments avec k intersections, la complexité en temps de l'algorithme de Bentley-Ottmann est O((n + k) log n). Dans le cas où k = o(n2 / log n), c'est une amélioration de l'algorithme naïf qui teste chaque pair de segments en temps O(n2). L'algorithme a été développé à l'origine par . Il est décrit plus en détail dans les articles de , , et . Bien que des algorithmes asymptotiquement plus rapides sont connus, l'algorithme de Bentley-Ottmann reste un choix pratique en raison de sa simplicité et de faibles besoins en mémoire. (fr)
- En géométrie algorithmique, l'algorithme de Bentley-Ottmann est un algorithme de sweep line pour trouver les (en). C'est une généralisation de l'algorithme de Shamos et Hoey qui vérifie si un ensemble de segments possède des intersections ou non. Pour n segments avec k intersections, la complexité en temps de l'algorithme de Bentley-Ottmann est O((n + k) log n). Dans le cas où k = o(n2 / log n), c'est une amélioration de l'algorithme naïf qui teste chaque pair de segments en temps O(n2). L'algorithme a été développé à l'origine par . Il est décrit plus en détail dans les articles de , , et . Bien que des algorithmes asymptotiquement plus rapides sont connus, l'algorithme de Bentley-Ottmann reste un choix pratique en raison de sa simplicité et de faibles besoins en mémoire. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 22424 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1985 (xsd:integer)
- 1998 (xsd:integer)
|
| prop-fr:arxiv
| |
| prop-fr:auteur
|
- Bernard Chazelle (fr)
- D. Eppstein (fr)
- D. Hoey (fr)
- D. Strash (fr)
- E. Y. Chen (fr)
- F. D. Preparata (fr)
- F. P. Preparata (fr)
- Herbert Edelsbrunner (fr)
- I. J. Balaban (fr)
- J. Bentley (fr)
- J. O'Rourke (fr)
- J. Pach (fr)
- J.-D. Boissonat (fr)
- K. L. Clarkson (fr)
- K. Mehlhorn (fr)
- K. Mulmuley (fr)
- K. Q. Brown (fr)
- M. Goodrich (fr)
- M. I. Shamos (fr)
- M. Sharir (fr)
- M. Smied (fr)
- Marc van Kreveld (fr)
- Mark Overmars (fr)
- Mark de Berg (fr)
- Otfried Schwarzkopf (fr)
- R. Cole (fr)
- R. E. Tarjan (fr)
- S. Näher (fr)
- T. M. Chan (fr)
- T. Ottmann (fr)
- U. Bartuschka (fr)
- Bernard Chazelle (fr)
- D. Eppstein (fr)
- D. Hoey (fr)
- D. Strash (fr)
- E. Y. Chen (fr)
- F. D. Preparata (fr)
- F. P. Preparata (fr)
- Herbert Edelsbrunner (fr)
- I. J. Balaban (fr)
- J. Bentley (fr)
- J. O'Rourke (fr)
- J. Pach (fr)
- J.-D. Boissonat (fr)
- K. L. Clarkson (fr)
- K. Mehlhorn (fr)
- K. Mulmuley (fr)
- K. Q. Brown (fr)
- M. Goodrich (fr)
- M. I. Shamos (fr)
- M. Sharir (fr)
- M. Smied (fr)
- Marc van Kreveld (fr)
- Mark Overmars (fr)
- Mark de Berg (fr)
- Otfried Schwarzkopf (fr)
- R. Cole (fr)
- R. E. Tarjan (fr)
- S. Näher (fr)
- T. M. Chan (fr)
- T. Ottmann (fr)
- U. Bartuschka (fr)
|
| prop-fr:date
|
- 1976 (xsd:integer)
- 1979 (xsd:integer)
- 1981 (xsd:integer)
- 1988 (xsd:integer)
- 1991 (xsd:integer)
- 1992 (xsd:integer)
- 1995 (xsd:integer)
- 1997 (xsd:integer)
- 1998 (xsd:integer)
- 2000 (xsd:integer)
- 2003 (xsd:integer)
- 2009 (xsd:integer)
|
| prop-fr:doi
|
- 10.110900 (xsd:double)
- 10.113700 (xsd:double)
- 10.114200 (xsd:double)
- 10.114500 (xsd:double)
|
| prop-fr:fr
|
- intersections d'un ensemble de segments (fr)
- intersections d'un ensemble de segments (fr)
|
| prop-fr:id
|
- 1 (xsd:integer)
- 3 (xsd:integer)
- 4 (xsd:integer)
- 6 (xsd:integer)
- 7 (xsd:integer)
- 9 (xsd:integer)
- 10 (xsd:integer)
- 11 (xsd:integer)
- 12 (xsd:integer)
- 13 (xsd:integer)
- 14 (xsd:integer)
- 15 (xsd:integer)
- 16 (xsd:integer)
|
| prop-fr:isbn
| |
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Bernard Chazelle (fr)
- David Eppstein (fr)
- Bernard Chazelle (fr)
- David Eppstein (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:mathReviews
| |
| prop-fr:numéro
| |
| prop-fr:numéroD'édition
| |
| prop-fr:pages
|
- 1 (xsd:integer)
- 19 (xsd:integer)
- 117 (xsd:integer)
- 147 (xsd:integer)
- 150 (xsd:integer)
- 208 (xsd:integer)
- 211 (xsd:integer)
- 460 (xsd:integer)
- 580 (xsd:integer)
- 643 (xsd:integer)
|
| prop-fr:pagesTotales
| |
| prop-fr:passage
|
- 263 (xsd:integer)
- 278 (xsd:integer)
|
| prop-fr:périodique
|
- 17 (xsd:integer)
- dbpedia-fr:International_Journal_of_Computational_Geometry_and_Applications
- IEEE Transactions on Computers (fr)
- Computational Geometry (fr)
- Journal of the ACM (fr)
- Proc. 11th ACM Symp. Computational Geometry (fr)
- Proc. 20th ACM-SIAM Symp. Discrete Algorithms (fr)
- Proc. 4th ACM Symp. Computational Geometry (fr)
- Proc. Worksh. Algorithm Engineering (fr)
- SIAM Journal on Computing (fr)
- Proc. 15th Canadian Conference on Computational Geometry (fr)
- Proc. 29th IEEE Symp. Foundations of Computer Science (fr)
|
| prop-fr:sousTitre
|
- An Introduction (fr)
- An Introduction (fr)
|
| prop-fr:titre
|
- An optimal algorithm for finding segments intersections (fr)
- An optimal algorithm for intersecting line segments in the plane (fr)
- A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem (fr)
- A fast planar partition algorithm, I (fr)
- Chapter 2: Line segment intersection (fr)
- Computational Geometry (fr)
- Computational Geometry in C (fr)
- Geometric intersection problems (fr)
- On vertical visibility in arrangements of segments and the queue size in the Bentley–Ottmann line sweeping algorithm (fr)
- Robust plane sweep for intersecting segments (fr)
- Algorithms for reporting and counting geometric intersections (fr)
- Computing intersections in a set of line segments: the Bentley–Ottmann algorithm (fr)
- Linear-time algorithms for geometric graphs with sublinearly many crossings (fr)
- Applications of random sampling in computational geometry, II (fr)
- Randomized parallel algorithms for trapezoidal diagrams (fr)
- A space-efficient algorithm for segment intersection (fr)
- Comments on "Algorithms for Reporting and Counting Geometric Intersections" (fr)
- An optimal algorithm for finding segments intersections (fr)
- An optimal algorithm for intersecting line segments in the plane (fr)
- A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem (fr)
- A fast planar partition algorithm, I (fr)
- Chapter 2: Line segment intersection (fr)
- Computational Geometry (fr)
- Computational Geometry in C (fr)
- Geometric intersection problems (fr)
- On vertical visibility in arrangements of segments and the queue size in the Bentley–Ottmann line sweeping algorithm (fr)
- Robust plane sweep for intersecting segments (fr)
- Algorithms for reporting and counting geometric intersections (fr)
- Computing intersections in a set of line segments: the Bentley–Ottmann algorithm (fr)
- Linear-time algorithms for geometric graphs with sublinearly many crossings (fr)
- Applications of random sampling in computational geometry, II (fr)
- Randomized parallel algorithms for trapezoidal diagrams (fr)
- A space-efficient algorithm for segment intersection (fr)
- Comments on "Algorithms for Reporting and Counting Geometric Intersections" (fr)
|
| prop-fr:titreChapitre
|
- Section 7.2.3 : Intersection of line segments (fr)
- Section 7.7 : Intersection of segments (fr)
- Section 7.2.3 : Intersection of line segments (fr)
- Section 7.7 : Intersection of segments (fr)
|
| prop-fr:trad
|
- Line segment intersection (fr)
- Line segment intersection (fr)
|
| prop-fr:volume
|
- 2 (xsd:integer)
- 20 (xsd:integer)
- 29 (xsd:integer)
- 39 (xsd:integer)
- -28.0
- -30.0
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En géométrie algorithmique, l'algorithme de Bentley-Ottmann est un algorithme de sweep line pour trouver les (en). C'est une généralisation de l'algorithme de Shamos et Hoey qui vérifie si un ensemble de segments possède des intersections ou non. Pour n segments avec k intersections, la complexité en temps de l'algorithme de Bentley-Ottmann est O((n + k) log n). Dans le cas où k = o(n2 / log n), c'est une amélioration de l'algorithme naïf qui teste chaque pair de segments en temps O(n2). (fr)
- En géométrie algorithmique, l'algorithme de Bentley-Ottmann est un algorithme de sweep line pour trouver les (en). C'est une généralisation de l'algorithme de Shamos et Hoey qui vérifie si un ensemble de segments possède des intersections ou non. Pour n segments avec k intersections, la complexité en temps de l'algorithme de Bentley-Ottmann est O((n + k) log n). Dans le cas où k = o(n2 / log n), c'est une amélioration de l'algorithme naïf qui teste chaque pair de segments en temps O(n2). (fr)
|
| rdfs:label
|
- Algorithme de Bentley-Ottmann (fr)
- Bentley–Ottmann algorithm (en)
- Алгоритм Бентли — Оттманна (ru)
- Алгоритм Бентлі — Оттманна (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
