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

DOI10.1016/0020-0190(85)90107-3zbMATH Open0583.90023OpenAlexW2016852342MaRDI QIDQ1069424FDOQ1069424

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

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
• Extremal point queries with lines and line segments and related problems
• On extremal point disributions in the Euclidean plane
• Finding Extremal Polygons

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)

Cites Work

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

Cited In (11)

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

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)