Fast stabbing of boxes in high dimensions

DOI10.1016/S0304-3975(98)00336-3zbMath0949.68147MaRDI QIDQ1583093

Frank Nielsen

Publication date: 26 October 2000

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

zbMATH Keywords

computational geometryoutput-sensitive algorithmsgeometric combinatorial optimization

Mathematics Subject Classification ID

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

Related Items (12)

A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve ⋮ Improved bound for the Gerver-Ramsey collinearity problem ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Lower bounds for piercing and coloring boxes ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Coloring and Maximum Independent Set of Rectangles ⋮ A note on maximum independent sets in rectangle intersection graphs ⋮ An improved algorithm for online unit clustering

Cites Work

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

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