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

DOI10.1016/0020-0190(85)90107-3MaRDI QIDQ1069424zbMATH OpenOpenAlexFDO

Authors 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

computational geometrydata structurespoint locationgeometric search proceduremulti-dimensional searchingpost-office problem

Mathematics Subject Classification ID

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

Recommendations

• The point-location problem for three-dimensional space
• scientific article; zbMATH DE number 2044013
• A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes
• Extreme points of well-posed polytopes
• scientific article; zbMATH DE number 3131086
• Extremal point queries with lines and line segments and related problems
• On extremal point disributions in the Euclidean plane
• Finding Extremal Polygons

Cites work

• scientific article; zbMATH DE number 3153257 (Why is no real title available?)
• scientific article; zbMATH DE number 3778747 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• A convex 3-complex not simplicially isomorphic to a strictly convex complex
• Convex hulls of finite sets of points in two and three dimensions
• 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
• Optimal Search in Planar Subdivisions
• Parallel concepts in graph theory
• Power Diagrams: Properties, Algorithms and Applications
• Spherical complexes and radial projections of polytopes
• Voronoi diagrams and arrangements

Cited in

(11)

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

This page was built for publication: Finding extreme points in three dimensions and solving the post-office problem in the plane

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