On the zone of a surface in a hyperplane arrangement

DOI10.1007/BF02189317MaRDI QIDQ1209841zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Micha Sharir, Marco Pellegrini

Publication date 16 May 1993

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/131243

zbMATH Keywords

algebraic surfacehyperplane arrangementzone theorem

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

For a collection of \(n\) hyperplanes in \(\mathbb{R}^ d\) the complex of all open cells and their lower dimensional faces is called an arrangement. The collection of all those cells which are met by a set \(\sigma\) is called its zone and its complexity is the number of all the faces. Asymptotic estimates for the complexity are given the simplest, for the case that \(\sigma\) is the boundary of a convex set or an algebraic surface, is \(O(n^{d-1}\log n)\).

Recommendations

• scientific article; zbMATH DE number 177534
• On the sum of squares of cell complexities in hyperplane arrangements
• On the zone of the boundary of a convex body
• Cell complexities in hyperplane arrangements
• On the Zone Theorem for Hyperplane Arrangements

Cites work

• Castles in the air revisited
• Efficient ray shooting and hidden surface removal
• scientific article; zbMATH DE number 4213489 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 4060713 (Why is no real title available?)
• scientific article; zbMATH DE number 177534 (Why is no real title available?)
• scientific article; zbMATH DE number 177535 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• On range searching with semialgebraic sets
• On the Betti Numbers of Real Varieties
• On the sum of squares of cell complexities in hyperplane arrangements
• On the Zone Theorem for Hyperplane Arrangements

Cited in

(25)

• Clamshell casting
• On the sum of squares of cell complexities in hyperplane arrangements
• On range searching with semialgebraic sets
• On joints in arrangements of lines in space and related problems
• On stabbing lines for convex polyhedra in 3D
• Castles in the air revisited
• A new technique for analyzing substructures in arrangements of piecewise linear surfaces
• Robot motion planning and the single cell problem in arrangements
• Almost tight upper bounds for the single cell and zone problems in the three dimensions
• Point location in zones of \(k\)-flats in arrangements
• Zone theorem for arrangements in dimension three
• On the zone of the boundary of a convex body
• On the number of pieces and faces of a subdivision of R^n by hyperplanes
• A note on visibility-constrained Voronoi diagrams
• On the Zone Theorem for Hyperplane Arrangements
• scientific article; zbMATH DE number 177534 (Why is no real title available?)
• scientific article; zbMATH DE number 637316 (Why is no real title available?)
• Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
• On range searching with semialgebraic sets
• Optimal algorithms for geometric centers and depth
• On the zone of a circle in an arrangement of lines
• On the zone of a circle in an arrangement of lines
• Diameter, width, closest line pair, and parametric searching
• Cell complexities in hyperplane arrangements
• A subquadratic algorithm for computing the L₁-distance between two terrains

This page was built for publication: On the zone of a surface in a hyperplane arrangement

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