Reporting and counting segment intersections
type: Item
instance of: scholarly article
title: Reporting and counting segment intersections
zbMATH Open document ID: 0616.68042
DOI: 10.1016/0022-0000(86)90025-5
author: Bernard Chazelle
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
review text: The author presents an algorithm for listing all segment intersections in the plane. The running time of the algorithm is \(O(n(\log^ 2n/\log \log n)+k)\), where n is the number of segments and k is the number of intersections. In order to construct the algorithm the author uses divide and conquer strategy and a new geometrical notion which he calls hammock. Using a result of \textit{H. Edelsbrunner} and \textit{E. Welzel} [Halfplanar range search in linear space and \(O(n^{0.695})\) query time, Tech. Univ. Graz. IIG Report 111 (1983)], he constructs an algorithm for evaluating the number of intersecting pairs of segmets with running time \(O(n^{1.695})\).
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3999289
zbMATH Keywords: line segments
zbMATH Keywords: computational geometry
zbMATH Keywords: segment intersections
zbMATH Keywords: hammock
reviewed by: M. A. Frumkin
MaRDI profile type: Publication
full work available at URL: 0022-0000(86)90025-5
OpenAlex ID: W2051017380
cites work: Algorithms for Reporting and Counting Geometric Intersections
cites work: Comments on “algorithms for reporting and counting geometric intersections”
cites work: Relational topology
cites work: Halfplanar range search in linear space and \(O(n^{0.695})\) query time
cites work: Optimal Search in Planar Subdivisions
cites work: Finding the intersection of two convex polyhedra
cites work: Plane-sweep algorithms for intersecting geometric figures
Recommended article: Counting and reporting red/blue segment intersections
Recommended article: Reporting Intersections of Polygons
Recommended article: Reporting red-blue intersections between two sets of connected ine segments
Recommended article: Reporting red-blue intersections between two sets of connected line segments
Recommended article: Reporting curve segment intersections using restricted predicates
Recommended article: Line-segment intersection reporting in parallel
Recommended article: REPORTING BICHROMATIC SEGMENT INTERSECTIONS FROM POINT SETS
Recommended article: Reporting intersections among thick objects.
Recommended article: Intersection reporting on two collections of disjoint sets
description: scientific article; zbMATH DE number 3999289