Fast stabbing of boxes in high dimensions

DOI10.1016/S0304-3975(98)00336-3MaRDI QIDQ1583093zbMATH OpenFDO

Authors Frank Nielsen

Publication date 26 October 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(98)00336-3

zbMATH Keywords

computational geometrygeometric combinatorial optimizationoutput-sensitive algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Algorithms for high dimensional stabbing problems
• Stabbing isothetic boxes and rectangles in \(O(n\log n)\) time
• Axis-Aligned Subdivisions with Low Stabbing Numbers
• Finding stabbing lines in 3-space

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• Almost optimal set covers in finite VC-dimension
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximations and optimal geometric divide-and-conquer
• Bounding the vertex cover number of a hypergraph
• Covering boxes by points
• Dynamic data structures for fat objects and their applications
• Fast approximation algorithms for a nonconvex covering problem
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• scientific article; zbMATH DE number 446693 (Why is no real title available?)
• scientific article; zbMATH DE number 3145756 (Why is no real title available?)
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256762 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• scientific article; zbMATH DE number 1163714 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• Improved non-approximability results
• Intersection properties of boxes in \(R^ n\).
• Label placement by maximum independent set in rectangles
• New Upper Bounds in Klee’s Measure Problem
• On point covers of c-oriented polygons
• On point covers of parallel rectangles
• Optimal packing and covering in the plane are NP-complete
• The slab dividing approach to solve the Euclidean \(P\)-center problem
• The Ultimate Planar Convex Hull Algorithm?

Cited in

(21)

• A note on maximum independent sets in rectangle intersection graphs
• An improved algorithm for online unit clustering
• Disjunctive splittability of languages
• Stabbing isothetic boxes and rectangles in \(O(n\log n)\) time
• Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking
• A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
• Near-linear approximation algorithms for geometric hitting sets
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Coloring and maximum independent set of rectangles
• A (2+)-approximation algorithm for the storage allocation problem
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Evader interdiction: algorithms, complexity and collateral damage
• Improved bound for the Gerver-Ramsey collinearity problem
• Lower bounds for piercing and coloring boxes
• Online geometric covering and piercing
• Stabbing boxes with finitely many axis-parallel lines and flats
• The online piercing set problem with recourse
• Simplification of forest classifiers and regressors by sharing branching conditions
• Approximating the maximum independent set of convex polygons with a bounded number of directions
• Online bichromatic piercing set problem
• Dynamic streaming algorithms for geometric independent set

This page was built for publication: Fast stabbing of boxes in high dimensions

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