%Compiler avec pdflatex, le rÃ©sultat ne doit pas dÃ©passer une page
%Merci de respecter scrupuleusement ce modÃ¨le.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Hitting and Packing Rectangles with a Bounded Aspect Ratio}
%

% Pour le sommaire
\addcontentsline{toc}{section}{M. Caoduro and A. Seb\H{o} : Hitting and Packing Rectangles with a Bounded Aspect Ratio}
%

% Pour la liste des auteurs
\index{Caoduro, M.}\index{Seb\H{o}, A.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Marco Caoduro}, G-SCOP, Grenoble, {\tt marco.caoduro@grenoble-inp.fr}\\
\indent
Andr\'as Seb\H{o}, G-SCOP, Grenoble, {\tt andras.sebo@grenoble-inp.fr}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le rÃ©sumÃ©


% definitions

Given a natural number $r$, a family of rectangles $\mathcal{R}$ is said to have \emph{bounded aspect ratio} $r$ if for any rectangle in $\mathcal{R}$ the ratio of the lengths of two perpendicular sides is at most $r$.
Ahlswede and Karapetyan \cite{2006_Ahlswede}
stated, without providing proof, that for a family of axis-parallel rectangles with bounded aspect ratio $r$ $\tau \leq 2(r+1) \nu$, where $\tau$ is the minimum number of points needed to hit all the rectangles in the family and $\nu$ is the maximum number of pairwise disjoint rectangles in the family.

\smallskip

We give an elementary proof of this result and generalize it to \emph{not necessarily axis-parallel} rectangles, with a slightly weaker constant $\tau \leq 4(r+1)\nu$.
Moreover, we observe that, in this more general setting, if one drops the hypothesis that the rectangles have a bounded aspect ratio, then $\frac{\tau}{\nu}$ can be arbitrarily large.
Finally, we give more precise upper and lower bounds on $\tau$ for the particular case $r=1$ that corresponds to families of squares.



\begin{thebibliography}{99}

%\bibitem{nk1}
%N.~Trotignon and K.~Vu{\v s}kovi{\'c}, \emph{A structure theorem for graphs with no cycle with a unique chord and  its consequences}, J. Graph Theory {\bf 63(1)} (2010), 31--67.
  
\bibitem{2006_Ahlswede}
R. Ahlswede and I. Karapetyan, \emph{Intersection Graphs of Rectangles and Segments} , In: Ahlswede R. et al. (eds) General Theory of Information Transfer and Combinatorics. Lecture Notes in Computer Science, vol 4123. Springer, Berlin, Heidelberg, 1064--1065


\end{thebibliography}


\vfill
\end{document}
