Paper Info
Title
Piercing quasi-rectangles-On a problem of Danzer and Rogers
Abstract
It is an old problem of Danzer and Rogers to decide whether it is possible arrange O(\frac1e</font >)O(\frac{1}{\varepsilon}) points in the unit square so that every rectangle of area ε contains at least one of them. We show that the answer to this question is in the negative if we slightly relax the notion of rectangles, as follows. Let δ be a fixed small positive number. A quasi-rectangle is a region swept out by a continuously moving segment s, with no rotation, so that throughout the motion the angle between the trajectory of the center of s and its normal vector remains at most δ. We show that the smallest number of points needed to pierce all quasi-rectangles of area ε is Q</font >(\frac1e</font >log\frac1e</font >).\Theta\left(\frac{1}{\varepsilon}\log\frac{1}{\varepsilon}\right).
Year
DOI
Venue
2012
10.1016/j.jcta.2012.03.011
workshop on algorithms and data structures
Keywords
DocType
Volume
normal vector,piercing quasi-rectangles-on,piercing quasi-rectangles,unit square,old problem,smallest number,fixed small positive number,points
Journal
119
Issue
ISSN
Citations 
7
0302-9743
3
PageRank 
References 
Authors
0.44
7
2
Name
Order
Citations
PageRank
János Pach12366292.28
Gábor Tardos21261140.58