TY - GEN

T1 - Computing envelopes in four dimensions with applications

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Sharir, Micha

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028124028&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028124028&partnerID=8YFLogxK

U2 - 10.1145/177424.178081

DO - 10.1145/177424.178081

M3 - Conference contribution

AN - SCOPUS:0028124028

SN - 0897916484

SN - 9780897916486

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 348

EP - 358

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Publ by ACM

T2 - Proceedings of the 10th Annual Symposium on Computational Geometry

Y2 - 6 June 1994 through 8 June 1994

ER -