Bentley–Ottmann algorithm
id:
bentley-ottmann-algorithm-319-13154986
title:
Bentley–Ottmann algorithm
text:
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 of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of n line segments with k crossings, the Bentley–Ottmann algorithm takes time O . In cases where k = o , this is an improvement on a naïve algorithm
brand slug:
wiki
category slug:
encyclopedia
description:
Sweep line algorithm
original url:
https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
date created:
date modified:
2024-03-11T06:50:27Z
main entity:
{"identifier":"Q4060664","url":"https://www.wikidata.org/entity/Q4060664"}
image:
fields total:
13
integrity:
14