Hitting and Piercing Rectangles Induced by a Point Set

DOI10.1007/978-3-642-38768-5_21zbMath1381.68303MaRDI QIDQ4925240

Abhijit Khopkar, Pradeesha Ashok, Ninad Rajgopal, Neeldhara Misra, Sathish Govindarajan

Publication date: 11 June 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38768-5_21

zbMATH Keywords

hitting set; centerpoint; selection lemma; induced rectangles

Mathematics Subject Classification ID

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

Related Items

Clique-width of point configurations, Selection Lemmas for Various Geometric Objects

Cites Work

• Unnamed Item
• Unnamed Item
• Witness Gabriel graphs
• Witness (Delaunay) graphs
• Hitting simplices with points in \(\mathbb R^{3}\)
• Improved results on geometric hitting set problems
• On the parameterized complexity of multiple-interval graph problems
• Small weak epsilon-nets
• The number of triangles covering the center of an \(n\)-set
• On empty triangles determined by points in the plane
• Optimal packing and covering in the plane are NP-complete
• A generalization of Caratheodory's theorem
• Points and triangles in the plane and halving planes in space
• On the complexity of locating linear facilities in the plane
• Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
• Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
• Approximation schemes for covering and packing problems in image processing and VLSI
• Selecting Heavily Covered Points
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
• A Theorem on General Measure