Matches in DBpedia 2014 for { ?s ?p In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set 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((n + k) log n). In cases where k = o(n2 / log n), this is an improvement on a naïve algorithm that tests every pair of segments, which takes O(n2).The algorithm was initially developed by Jon Bentley and Thomas Ottmann (1979); it is described in more detail in the textbooks Preparata & Shamos (1985), O'Rourke (1998), and de Berg et al. (2000). Although asymptotically faster algorithms are now known, the Bentley–Ottman algorithm remains a practical choice due to its simplicity and low memory requirements.. }
Showing items 1 to 1 of
1
with 100 items per page.
- Bentley–Ottmann_algorithm abstract "In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set 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((n + k) log n). In cases where k = o(n2 / log n), this is an improvement on a naïve algorithm that tests every pair of segments, which takes O(n2).The algorithm was initially developed by Jon Bentley and Thomas Ottmann (1979); it is described in more detail in the textbooks Preparata & Shamos (1985), O'Rourke (1998), and de Berg et al. (2000). Although asymptotically faster algorithms are now known, the Bentley–Ottman algorithm remains a practical choice due to its simplicity and low memory requirements.".