Metraipolis › archive › dc_7e460a36a8da
Algorithme de Bentley-Ottmann — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Algorithme_de_Bentley-Ottmann
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-17T11:33:35.416Z
- SHA-256 of the archived text
733a430c98615d8e584ed052e8bc1d4c04fa791d5d6827d6dcac0f8b1153814f- Stable URL of this page
https://metraipolis.com/documento/dc_7e460a36a8da
How to cite
Algorithme de Bentley-Ottmann — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Bentley-Ottmann (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7e460a36a8da (Metraipolis archive dc_7e460a36a8da, sha256 733a430c98615d8e584ed052e8bc1d4c04fa791d5d6827d6dcac0f8b1153814f)
BibTeX
@misc{dc7e460a36a8da,
title = {Algorithme de Bentley-Ottmann — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Algorithme_de_Bentley-Ottmann},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7e460a36a8da; sha256 733a430c98615d8e584ed052e8bc1d4c04fa791d5d6827d6dcac0f8b1153814f},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Bentley-Ottmann. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En géométrie algorithmique, l'algorithme de Bentley-Ottmann est un algorithme de sweep line pour trouver les intersections d'un ensemble de segments (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 paire de segments en temps O(n2). L'algorithme a été développé à l'origine par Jon Bentley et Thomas Ottmann (1979). Il est décrit plus en détail dans les articles de Preparata et Shamos (1985), O'Rourke (1998), et de Berg et al. (2000). 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. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Algorithme de Bentley-Ottmann» — https://fr.wikipedia.org/wiki/Algorithme_de_Bentley-Ottmann Wikidata Q4060664 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4060664 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_de_Bentley-Ottmann?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 214195601, consultata il 2026-10-17T11:10:20.381Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: fb4d66b9b22ca3b6df2ae79e097c55f9c66a489851d847b41bd16d9b3d0bc24c