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

closest pairlower envelopespoint locationray 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

(27)

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

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)