### Abstract

We present a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorithm is O(n α(n) log n). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor analysis technique [3].

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

Title of host publication | Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 |

Publisher | Association for Computing Machinery |

Pages | 441-448 |

Number of pages | 8 |

ISBN (Print) | 0897913760 |

State | Published - Mar 1 1991 |

Event | 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States Duration: Jan 28 1991 → Jan 30 1991 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 |
---|---|

Country | United States |

City | San Francisco |

Period | 1/28/91 → 1/30/91 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Computing a face in an arrangement of line segments'. Together they form a unique fingerprint.

## Cite this

Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Snoeyink, J. (1991). Computing a face in an arrangement of line segments. In

*Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991*(pp. 441-448). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.