# Partitioning arrangements of lines II: Applications

Published

Journal Article

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) an O(m2/3n2/3 · log2/3n · logω/3 (m/√n)+(m+n) log n) algorithm to compute all incidences between m points and n lines, where ω is a constant <3.33; (ii) an O(m2/3n2/3 · log5/3n · logω/3 (m/√n)+(m+n) log n) algorithm to compute m faces in an arrangement of n lines; (iii) an O(n4/3 log(ω+2)/3n) algorithm to count the number of intersections in a set of n segments; (iv) an O(n4/3 log(ω + 2)/3n) algorithm to count "red-blue" intersections between two sets of segments, and (v) an O(n3/2 logω/3n) algorithm to compute spanning trees with low stabbing number for a set of n points. We also present an algorithm that, given set of n points in the plane, preprocesses it, in time O(n√m logω+1/2n), into a data structure of size O(m) for n log n≤m≤n2, so that the number of points of S lying inside a query triangle can be computed in O((n/√m) log3/2n) time. © 1990 Springer-Verlag New York Inc.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK

### Published Date

- December 1, 1990

### Published In

### Volume / Issue

- 5 / 1

### Start / End Page

- 533 - 573

### Electronic International Standard Serial Number (EISSN)

- 1432-0444

### International Standard Serial Number (ISSN)

- 0179-5376

### Digital Object Identifier (DOI)

- 10.1007/BF02187809

### Citation Source

- Scopus