### Abstract

The authors present the first optimal algorithm for the following problem: given n line segments in the plane, computes all k pairwise intersections in O(n log n + k) time. Within the same asymptotic cost the algorithm will also compute the adjacencies of the planar subdivision induced by the segments, which is a useful data structure for contour-filling on raster devices.

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

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | Publ by IEEE |

Pages | 590-600 |

Number of pages | 11 |

ISBN (Print) | 0818608773, 9780818608773 |

DOIs | |

State | Published - 1988 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### All Science Journal Classification (ASJC) codes

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'Optimal algorithm for intersecting line segments in the plane'. Together they form a unique fingerprint.

## Cite this

Chazelle, B., & Edelsbrunner, H. (1988). Optimal algorithm for intersecting line segments in the plane. In

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 590-600). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1988.21975