### Abstract

This paper partly settles the following question: Is it possible to compute all k intersections between n arbitrary line segments in time linear in k? We describe an algorithm for this problem whose running time is O(n( log^{2} n log log n)+k). This is the first solution with a time bound linear in the size of the output. To obtain this result we turn away from traditional, sweep-line-based schemes. Instead, we introduce a new hierarchical strategy for dealing with segments without reducing the dimensionality of the problem. This framework is also used to answer related questions. New results include an O(n^{1.695}) time algorithm for counting intersections (as opposed to reporting each of them explicitly) and an optimal algorithm for computing the intersections of a line arrangement with a query segment. Using duality arguments we also present an improved algorithm for a point enclosure problem.

Original language | English (US) |
---|---|

Pages (from-to) | 156-182 |

Number of pages | 27 |

Journal | Journal of Computer and System Sciences |

Volume | 32 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1986 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics