### Abstract

Let F be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of F in expected time O(n^{d+ε}), for any ε > 0. For d = 3, by combining this algorithm with the point location technique of Preparata and Tamassia, we can compute, in randomized expected time O(n^{3+ε}), for any ε > 0, a data structure of size O(n^{3+ε}) that, given any query point q, can determine in O(log^{2} n) time whether q lies above, below or on the envelope. As a consequence, we obtain improved algorithmic solutions to many problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the biggest stick in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in time O(n^{17/11+ε}), for any ε > 0, improving previous solutions that run in time O(n^{8/5+ε}). We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane, and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require O(n^{3+ε}) storage and preprocessing time, for any ε > 0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

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

Title of host publication | Proceedings of the Annual Symposium on Computational Geometry |

Publisher | Publ by ACM |

Pages | 348-358 |

Number of pages | 11 |

ISBN (Print) | 0897916484, 9780897916486 |

DOIs | |

State | Published - 1994 |

Event | Proceedings of the 10th Annual Symposium on Computational Geometry - Stony Brook, NY, USA Duration: Jun 6 1994 → Jun 8 1994 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | Proceedings of the 10th Annual Symposium on Computational Geometry |
---|---|

City | Stony Brook, NY, USA |

Period | 6/6/94 → 6/8/94 |

### ASJC Scopus subject areas

- Software
- Geometry and Topology
- Safety, Risk, Reliability and Quality
- Chemical Health and Safety

## Fingerprint Dive into the research topics of 'Computing envelopes in four dimensions with applications'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the Annual Symposium on Computational Geometry*(pp. 348-358). (Proceedings of the Annual Symposium on Computational Geometry). Publ by ACM. https://doi.org/10.1145/177424.178081