Computing Envelopes in Four Dimensions with Applications

DOI10.1137/S0097539794265724MaRDI QIDQ4376194zbMATH OpenOpenAlexFDO

Authors Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Publication date 10 February 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794265724

zbMATH Keywords

point locationclosest pairlower envelopesray shooting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Recommendations

• Almost tight upper bounds for lower envelopes in higher dimensions
• Almost tight upper bounds for vertical decompositions in four dimensions
• Efficient randomized algorithms for some geometric optimization problems
• The upper envelope of piecewise linear functions: Algorithms and applications
• The overlay of lower envelopes and its applications

Cited in

(23)

• Exact computation of the medial axis of a polyhedron
• scientific article; zbMATH DE number 786170 (Why is no real title available?)
• Faster algorithms for growing prioritized disks and rectangles
• Minimum-width annulus with outliers: circular, square, and rectangular cases
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• Lines avoiding balls in three dimensions revisited
• Envelope computation in the plane by approximate implicitization
• On overlays and minimization diagrams
• Voronoi diagram of polygonal chains under the discrete Fréchet distance
• APPROXIMATING 3D POINTS WITH CYLINDRICAL SEGMENTS
• Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance
• The k-centrum straight-line location problem
• Continuous location of dimensional structures.
• scientific article; zbMATH DE number 7278008 (Why is no real title available?)
• Lower envelopes of surface patches in 3-space
• Towards space efficient two-point shortest path queries in a polygonal domain
• Semi-algebraic off-line range searching and biclique partitions in the plane
• The Offset Filtration of Convex Objects
• Almost tight upper bounds for lower envelopes in higher dimensions
• Querying two boundary points for shortest paths in a polygonal domain
• scientific article; zbMATH DE number 7559380 (Why is no real title available?)
• Computing constrained minimum-width annuli of point sets
• Combinatorial characterizations and algorithms for trajectory planning of an articulated robotic probe in three dimensions

This page was built for publication: Computing Envelopes in Four Dimensions with Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376194)