Algorithms for high dimensional stabbing problems

DOI10.1016/0166-218X(90)90127-XzbMath0703.90074MaRDI QIDQ916570

David Avis, Mike Doskas

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

hyperplane transversalgeometric algorithmscomputational geometryconvex polyhedrastabbing

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Other problems of combinatorial convexity (52A37)

Related Items

Diameter partitioning, Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications, Helly-type theorems and generalized linear programming, Ordered stabbing of pairwise disjoint convex sets in linear time, Computing shortest transversals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
• The upper envelope of piecewise linear functions: Algorithms and applications
• Diameter partitioning
• Finding transversals for sets of simple geometric figures
• Geometric permutations and common transversals
• Thin sets and common transversals
• Stabbing line segments
• Polyhedral line transversals in space
• Geometric permutations for convex sets
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Linear Programming in Linear Time When the Dimension Is Fixed
• Hadwiger's Transversal Theorem In Higher Dimensions
• Optimal Search in Planar Subdivisions
• Multidimensional Searching Problems
• A conjecture of Grünbaum on common transversals.
• Partitions ofN-Space by Hyperplanes