Computing envelopes in four dimensions with applications

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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(nd+ε), 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(n3+ε), for any ε > 0, a data structure of size O(n3+ε) that, given any query point q, can determine in O(log2 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(n17/11+ε), for any ε > 0, improving previous solutions that run in time O(n8/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(n3+ε) storage and preprocessing time, for any ε > 0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual Symposium on Computational Geometry
    PublisherPubl by ACM
    Number of pages11
    ISBN (Print)0897916484, 9780897916486
    StatePublished - 1994
    EventProceedings of the 10th Annual Symposium on Computational Geometry - Stony Brook, NY, USA
    Duration: Jun 6 1994Jun 8 1994

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry


    OtherProceedings of the 10th Annual Symposium on Computational Geometry
    CityStony Brook, NY, USA

    ASJC Scopus subject areas

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


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

    Cite this