About: Bentley–Ottmann algorithm

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Bentley–Ottmann algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : wikidata:Q8366, within Data Space : fr.dbpedia.org associated with source document(s)

Attributes	Values
rdf:type	Thing Algorithm Algorithm
rdfs:label	Algorithme de Bentley-Ottmann (fr) Bentley–Ottmann algorithm (en) Алгоритм Бентли — Оттманна (ru) Алгоритм Бентлі — Оттманна (uk)
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)
sameAs	Bentley–Ottmann algorithm Bentley–Ottmann algorithm Bentley–Ottmann algorithm Bentley–Ottmann algorithm Bentley–Ottmann algorithm Bentley–Ottmann algorithm
Wikipage page ID	11050972 (xsd:integer)
Wikipage revision ID	175869741 (xsd:integer)
dbo:wikiPageWikiLink	dbpedia-fr:Algorithme_de_Shamos_et_Hoey Sweep line algorithm Deterministic algorithm Randomized algorithm Red–black tree Binary search tree Decision tree dbpedia-fr:Arbre_équilibré dbpedia-fr:Arithmétique_multiprécision dbpedia-fr:Cambridge_University_Press category-fr:Algorithme category-fr:Géométrie_algorithmique Time complexity Correctness (computer science) Closed set dbpedia-fr:File_de_priorité dbpedia-fr:Graphe_connexe dbpedia-fr:Graphe_planaire dbpedia-fr:Géométrie_algorithmique dbpedia-fr:International_Journal_of_Computational_Geometry_and_Applications dbpedia-fr:Logarithme_itéré Computer data storage dbpedia-fr:Nombre_rationnel Mathematical induction dbpedia-fr:Recherche_dichotomique dbpedia-fr:Sans_perte_de_généralité Data structure Binary heap Fibonacci heap dbpedia-fr:Virgule_flottante dbpedia-fr:Majorant_ou_minorant
Link from a Wikipage to an external page	http://www.cccg.ca/proceedings/2003/31.pdf%7Cpages=%7Cid=8 http://www.cs.brown.edu/research/pubs/pdfs/2000/Boissonnat-2000-RPS.pdf%7Cpages=1401-1421%7Cid=5 http://www.dsi.unive.it/~wae97/proceedings/ONLY_PAPERS/pap13.ps.gz%7Cpages=%7Cid=2 http://www.scs.carleton.ca/~michiel/lecturenotes/ALGGEOM/bentley-ottmann.pdf%7Cid=17%7Cformat=pdf
page length (characters) of wiki page	22424 (xsd:nonNegativeInteger)
dct:subject	category-fr:Algorithme category-fr:Géométrie_algorithmique
prop-fr:wikiPageUsesTemplate	dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Lien dbpedia-fr:Modèle:Lien_web dbpedia-fr:Modèle:Ouvrage dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Sources_à_lier dbpedia-fr:Modèle:Traduction/Référence dbpedia-fr:Modèle:Référence_Harvard_sans_parenthèses
prov:wasDerivedFrom	wikipedia-fr:Algorithme_de_Bentley-Ottmann?oldid=175869741&ns=0
prop-fr:année	1985 (xsd:integer) 1998 (xsd:integer)
prop-fr:arxiv	812 (xsd:double)
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)
prop-fr:date	1976 (xsd:integer) 1979 (xsd:integer)

Faceted Search & Find service v1.16.111 as of Oct 19 2022

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 11 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software