Hitting and Piercing Rectangles Induced by a Point Set

DOI10.1007/978-3-642-38768-5_21MaRDI QIDQ4925240zbMATH OpenOpenAlexFDO

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

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

centerpointhitting setinduced rectanglesselection lemma

Mathematics Subject Classification ID

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

Recommendations

• On piercing sets of axis-parallel rectangles and rings
• ON PIERCING SETS OF AXIS-PARALLEL RECTANGLES AND RINGS
• Covering, hitting, piercing and packing rectangles intersecting an inclined line
• Independent and hitting sets of rectangles intersecting a diagonal line
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Computing and Combinatorics
• Point sets in the unit square and large areas of convex hulls of subsets of points
• Point Sets in the Unit Square and Large Areas of Convex Hulls of Subsets of Points
• On the number of rectangulations of a planar point set

Cites work

• A generalization of Caratheodory's theorem
• A Theorem on General Measure
• Approximation schemes for covering and packing problems in image processing and VLSI
• 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
• Hitting simplices with points in \(\mathbb R^{3}\)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 2103167 (Why is no real title available?)
• Improved results on geometric hitting set problems
• On empty triangles determined by points in the plane
• On the complexity of locating linear facilities in the plane
• On the parameterized complexity of multiple-interval graph problems
• Optimal packing and covering in the plane are NP-complete
• Points and triangles in the plane and halving planes in space
• Selecting Heavily Covered Points
• Small weak epsilon-nets
• Small-size -nets for axis-parallel rectangles and boxes
• The number of triangles covering the center of an \(n\)-set
• Witness (Delaunay) graphs
• Witness Gabriel graphs

Cited in

(3)

• On sets of \(n\) points in general position that determine lines that can be pierced by \(n\) points
• Selection lemmas for various geometric objects
• Clique-width of point configurations

This page was built for publication: Hitting and Piercing Rectangles Induced by a Point Set

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