About: Bentley–Ottmann algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Bentley–Ottmann algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Software, within Data Space : el.dbpedia.org associated with source document(s)

In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments. It extends the , a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings (or intersections), the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes .

Attributes	Values
rdf:type	software
rdfs:label	Bentley–Ottmann algorithm (en)
rdfs:comment	In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments. It extends the , a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings (or intersections), the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes . (en)
sameAs	Bentley–Ottmann algorithm
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Citation_needed dbt:Clarify dbt:Confusing_section dbt:Harvs dbt:Harvtxt dbt:Reflist dbt:Sfnp dbt:Log-star
Subject	Computational geometry Geometric algorithms
Link from a Wikipage to an external page	http://www.cccg.ca/proceedings/2003/31.pdf http://www.scs.carleton.ca/~michiel/lecturenotes/ALGGEOM/bentley-ottmann.pdf%7Ctitle=Computing https://archive.org/details/computationalgeo00berg/page/19 http://www.dsi.unive.it/~wae97/proceedings/%7Ctitle=Proc. http://www.dsi.unive.it/~wae97/proceedings/ONLY_PAPERS/pap13.ps.gz%7Ceditor1-first=G. http://www.cs.brown.edu/research/pubs/pdfs/2000/Boissonnat-2000-RPS.pdf%7Cdoi=10.1137/S0097539797329373%7Cvolume=29%7Cissue=5%7Cpages=1401%E2%80%931421 https://web.archive.org/web/20170606120507/http:/www.dsi.unive.it/~wae97/proceedings/%7Curl-status=dead
gold:hypernym	Algorithm
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm?oldid=1055323325&ns=0
Wikipage page ID	16329810 (xsd:integer)
page length (characters) of wiki page	24188 (xsd:nonNegativeInteger)
Wikipage revision ID	1055323325 (xsd:integer)
Link from a Wikipage to another Wikipage	Floating-point arithmetic Priority queue Arbitrary-precision arithmetic Arrangement of lines Asymptotic analysis Binary heap Binary search tree Self-balancing binary search tree Upper and lower bounds Computational geometry General position Journal of the ACM Geometric algorithms Sweep line algorithm Decision tree model Planar graph Closed set Computational geometry Connectivity (graph theory) Data structure Symposium on Foundations of Computer Science Deterministic algorithm Fibonacci heap International Journal of Computational Geometry and Applications Intersection (Euclidean geometry) Iterated logarithm Library of Efficient Data types and Algorithms Rational number Red–black tree dbr:Shamos–Hoey_algorithm
has abstract	In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments. It extends the , a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings (or intersections), the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes . The algorithm was initially developed by Jon Bentley and Thomas Ottmann; it is described in more detail in the textbooks , , and . Although asymptotically faster algorithms are now known by and , the Bentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm
is Wikipage redirect of	Bentley-Ottmann algorithm
is Link from a Wikipage to another Wikipage of	Bentley-Ottmann algorithm Jon Bentley List of algorithms Multiple line segment intersection
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software