\documentclass{article}
\usepackage{xspace}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{ifthen}
\usepackage{totcount}
\usepackage{xcolor}
\usepackage[a4paper, margin=1in]{geometry}
\graphicspath{ {./figures/} }
%--------------------------------------------------------------------------------
% Style stuff
\pagestyle{fancy}
\lhead{Geometric Algorithms (INFOGA 2019)}
\chead{}
\rhead{\mytitle}
\lfoot{INFOGA 2019}
\cfoot{}
\rfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\renewcommand{\familydefault}{\sfdefault}
%--------------------------------------------------------------------------------
% Question macro's
\newcommand{\withpoints}[1]{%
\addtocounter{pointscounter}{#1} \printpoints{#1}
}
\newcommand{\printpoints}[1]{%
\ifthenelse{#1 = 0}
{}
{\textit{(#1 points)}}\mbox{}\\
}
\newenvironment{questions}{\begin{enumerate}[label=\textbf{Question \arabic*}
,labelwidth=!
,align=left
]}
{\end{enumerate}}
\newenvironment{parts}{\begin{enumerate}[leftmargin=*
]}
{\end{enumerate}}
\newcommand{\question}[1][0]{\item\stepcounter{questionscounter}\withpoints{#1}}
\newcommand{\qpart}[1][0]{\item \withpoints{#1}}
\newtotcounter{questionscounter}
\newtotcounter{pointscounter}
\newcommand{\numquestions}{\total{questionscounter}}
\newcommand{\numpoints}{\total{pointscounter}}
%--------------------------------------------------------------------------------
\newcommand{\myremark}[3]{\textcolor{blue}{\textsc{#1 #2:}} \textcolor{red}{\textsf{#3}}}
% \renewcommand{\myremark}[3]{}
\newcommand{\frank}[2][says]{\myremark{Frank}{#1}{#2}}
%--------------------------------------------------------------------------------
% Theorem Environments
\newtheorem{theorem} {Theorem}
\newtheorem{lemma}[theorem] {Lemma}
\newtheorem{corollary}[theorem] {Corollary}
\newtheorem{problem}[theorem] {Problem}
\newtheorem{observation}[theorem] {Observation}
\newtheorem{claim}[theorem] {Claim}
\newtheorem{invariant}[theorem] {Invariant}
%--------------------------------------------------------------------------------
% Otherwise useful Macro's
\newcommand{\eps}{\ensuremath{\varepsilon}\xspace}
\DeclareMathOperator{\argmin}{argmin}
\newcommand{\mkmbb}[1]{\ensuremath{\mathbb{#1}}\xspace}
\newcommand{\R}{\mkmbb{R}}
%--------------------------------------------------------------------------------
% The Actual document
\newcommand{\mytitle}{Homework Exam 3 2019}
\title{\mytitle}
\date{\textbf{Deadline: } 10 January 2020, 12:45}
\author{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\noindent
This homework exam has \numquestions\xspace questions for a total of
\numpoints\xspace points. You can earn 10 additional points by a
careful preparation of your hand-in: using a good layout, good
spelling, good figures, no sloppy notation, no statements like ``The
algorithm runs in $n\log n$.'' (forgetting the $O(..)$ and
forgetting to say that it concerns time), etc. Use lemmas, theorems,
and figures where appropriate. Your final grade will be the number
of points divided by 10. Unless stated otherwise, both randomized
and deterministic solutions are allowed. In case you are asked to
analyze the running time and your algorithm is randomized, analyze
its expected running time.
\begin{questions}
\question Let $P$ be a simple polygon with $n$ edges in which no
two vertices have exactly the same $x$ or $y$-coordinate, and no
three points are colinear. We wish to preprocess $P$ for efficient
point location queries. Clearly, we can just build a trapezoidal
decomposition on the edges of $P$ in expected $O(n \log n)$
time. Here, we will show that we can do slightly better by using a
variation of the randomized incremental approach we discussed in
class.
Consider the following approach:
split the boundary of $P$ into $\lceil n/m \rceil$ pieces with $m$
consecutive edges each. Consider these pieces in a random order,
and for each of the $n/m$ pieces do the following:
\begin{enumerate}[noitemsep,label=\arabic*.]
\item do a single point location query to find the trapezoid containing the starting
point of the piece,
\item trace the piece in the decomposition to find all existing
trapezoids intersected by the piece,
\item delete all these trapezoids and replace them by new trapezoids.
\end{enumerate}
Analyze the above algorithm. In particular:
\begin{parts}
\qpart[10] Prove that in total the expected number of trapezoids
created is still $O(n)$.
\qpart[5] Prove that the total expected time it takes to find
all trapezoids that we have to delete is $O(nm)$.
\qpart[10] Argue that in expected $O(n\sqrt{\log n})$ time we can
build a point location data structure that has expected size
$O(n)$ and can answer point location queries in expected
$O(\log n)$ time.
\end{parts}
\question[20] Suppose that you are a shop owner. Let $P$ be the
set of $n$ people that has entered your shop at some given day. In
particular, for every person $p \in P$ you know the time $a_p$
which he or she arrived at your shop, and the time $d_p$ at
which he or she departed. You can assume that no two people arrive
or leave at the same time. You would like to store $P$ so that given a
time $t$ and a duration $\ell$, you can quickly (i.e. as fast as
possible) find the number of people that were in your shop at time
$t$ and stayed for at least $\ell$ time units during that visit.
Develop a linear space data structure for the above problem. That
is, describe your data structure, how to build and query it, and
analyze the preprocessing and query time.
{\color{red}\textbf{Clarification 2019-12-20: } Your data structure should
have a sublinear (i.e. $o(n)$) query time.}
\question Let $P$ be a set of points in $\R^2$. You can assume
that no three points are colinear, no two points have the same
$x$-coordinate, and no two points have the same $y$-coordinate.
\begin{parts}
\qpart[10] Describe a data structure that given a query
halfplane $h$ can test in $O(\log n)$ time if $h$ contains a
point of $P$. Analyze the space, and preprocessing time of your
data structure.
\qpart[10] Describe a data structure that, given an arbitrary
query line segment $q=\overline{\ell{}r}$, with endpoint $\ell$
left of endpoint $r$, can test if there are any points in $P$
that lie vertically below $q$. If, for some point $p$ we have
that $p_x \not\in [\ell_x,r_x]$ it is incomparable with $q$ (and
hence it does not lie vertically below $q$).
\end{parts}
\question Let $P$ be a set of $n$ weighted points in $\R^2$, that
is, every points $p \in P$ has a weight $p_w \in \R$. Furthermore,
let $\|ab\|$ denote the Euclidean distance between to points $a,b
\in \R^2$.
\begin{parts}
\qpart[15] We can define a distance function
$d^+(p,q) = p_w + \|pq\|$ that measures the ``weighted''
distance from any point $q \in \R^2$ to a point $p \in P$, and
thus we can define a Voronoi diagram based on the distance
measure $d^+$. Prove that the Voronoi region $V^+(p)$ of $p$
(i.e. the set of all points in $\R^2$ closer to $p$ than to any
other site $z \neq p \in P$) is connected.
\qpart[10] We can also define the distance function
$d^*(p,q) = p_w\|pq\|$. Prove that in this case, the Voronoi
region $V^*(p)$ of $p$ (i.e. the set of all points in $\R^2$
closer to $p$ than to any other site $z \neq p \in P$) may be
disconnected.
\end{parts}
\end{questions}
\end{document}