Finding extreme points in three dimensions and solving the post-office problem in the plane

DOI10.1016/0020-0190(85)90107-3zbMath0583.90023OpenAlexW2016852342MaRDI QIDQ1069424

Herbert Edelsbrunner, Hermann Maurer

Publication date: 1985

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(85)90107-3

zbMATH Keywords

data structurescomputational geometrypoint locationgeometric search proceduremulti-dimensional searchingpost-office problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Inventory, storage, reservoirs (90B05)

Related Items

Computing circular separability ⋮ Finding minimal enclosing boxes ⋮ A criterion for the affine equivalence of cell complexes in \(R^ d\) and convex polyhedra in \(R^{d+1}\) ⋮ Edge-skeletons in arrangements with applications ⋮ Recognising polytopical cell complexes and constructing projection polyhedra ⋮ A complete and efficient algorithm for the intersection of a general and a convex polyhedron ⋮ Polygonal intersection searching ⋮ On the equivalence of some rectangle problems ⋮ Parabolic spiral search plan for a randomly located target in the plane ⋮ A parallel algorithm for constructing projection polyhedra

Cites Work

• Voronoi diagrams and arrangements
• Parallel concepts in graph theory
• Spherical complexes and radial projections of polytopes
• On the perspective deformation of polyhedra
• On the perspective deformation of polyhedra. II. Solution of the convexity problem
• Optimal Point Location in a Monotone Subdivision
• A convex 3-complex not simplicially isomorphic to a strictly convex complex
• Optimal Search in Planar Subdivisions
• Convex hulls of finite sets of points in two and three dimensions
• Power Diagrams: Properties, Algorithms and Applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item