\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}
\pagestyle{fancy}
\lhead{Geometric Algorithms (INFOGA 2019)}
\chead{}
\rhead{\mytitle}
\lfoot{INFOGA 2019}
\cfoot{}
\rfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
% \usepackage[T1]{fontenc}
% \usepackage[sfdefault,scaled=.85]{FiraSans}
% \usepackage{newtxsf}
\renewcommand{\familydefault}{\sfdefault}
\graphicspath{ {./figures/} }
\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}}
\newcommand{\eps}{\ensuremath{\varepsilon}\xspace}
\newcommand{\myremark}[3]{\textcolor{blue}{\textsc{#1 #2:}} \textcolor{red}{\textsf{#3}}}
% \renewcommand{\myremark}[3]{}
\newcommand{\frank}[2][says]{\myremark{Frank}{#1}{#2}}
\DeclareMathOperator{\argmin}{argmin}
\newtotcounter{questionscounter}
\newtotcounter{pointscounter}
\newcommand{\numquestions}{\total{questionscounter}}
\newcommand{\numpoints}{\total{pointscounter}}
% \pagestyle{headandfoot}
% \runningheadrule
% \firstpageheader
% \runningheader{INFOGA 2019}{}{\@title}
% \runningfootrule
% \firstpagefooter{}{}{}
% \runningfooter{INFOGA 2019}{\@title}{Page \thepage\ of \numpages}
\newcommand{\mkmbb}[1]{\ensuremath{\mathbb{#1}}\xspace}
\newcommand{\R}{\mkmbb{R}}
\newcommand{\mytitle}{Retake Homework Exam 2019}
\title{\mytitle}
\date{\textbf{Deadline: } 13 March 2020, 17:00}
\author{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\noindent
This homework exam has \numquestions\xspace questions for a total of
\numpoints\xspace points. You can earn an additional 10 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 (with a maximum of a
10).
\begin{questions}
\question[10] Let $P$ be a set of $n$ points in $\R^3$, and let
$h$ be a real number. You can assume that all coordinates are
unique. Consider a horizontal slab $S$ of height $h$
(i.e. $S=\{(x,y,z_{\min}+z') \mid x,y \in \R, z' \in [0,h]\}$ for
some $z_{\min} \in \R$), and let $V(S)$ denote the volume of the
axis-aligned bounding box of $P \cap S$. Develop an $O(n\log n)$
time algorithm that can compute the maximum value of $V(S)$ over
all horizontal slabs $S$ of height $h$. Argue that your algorithm
is correct and achieves the desired running time.
\question Let $\mathcal{S}$ be a planar subdivision with $n$
vertices, represented as a DCEL.
\begin{parts}
\qpart[10] Give pseudo-code for an algorithm that, given a
pointer to a face $f$, computes \emph{the set} of all faces of
$\mathcal{S}$ adjacent to $f$. Your algorithm should use the
'Twin', 'NextEdge', 'PrevEdge', etc. fields to navigate
(i.e. you cannot assume you can directly access a list of
vertices). Describe in a few sentences the main idea of your
algorithm. Furthermore, argue that it is correct.
\qpart[5] Analyze the running time of your algorithm. In
particular, argue whether or not it is output sensitive, i.e. if
its running time depends on $k$ the number of faces reported.
\end{parts}
\question A simple polygon $P$ is \emph{star-shaped} if and only if it
contains a point $q \in P$ such that for any point $p \in P$, the line segment
$\overline{pq}$ lies inside $P$.
\begin{parts}
\qpart[10] We say that $P$ is \emph{strictly star-shaped} if (and only
if) the point $q$ is also a vertex of $P$. Show that there are polygons
that are star-shaped but not strictly star-shaped.
\qpart[10] Design an algorithm that can decide if a simple polygon $P$
with $n$ vertices is star-shaped in $O(n)$ expected time. You can again
assume no three vertices of $P$ are colinear.
\end{parts}
\question[20] Let $S$ be a set of $n$ line segments in $\R^2$. You can
assume no three endpoints in $S$ are colinear, and all coordinate
values of all endpoints are unique. Describe an $O(n^2)$ time
algorithm to compute the maximum number of segments from $S$ that
can be stabbed by a line. Your algorithm should report this
number, $k$, and a line $\ell$ realizing $k$ intersections.
\question Let $P$ be a polyline with $n$ vertices. You can assume
that $P$ does not have any self intersections, that all
coordinates of the vertices are unique, and that no three vertices
are colinear.
\begin{parts}
\qpart[5] Describe a data structure that can efficiently test if
a query point $q \in \R^2$ lies on an edge of $P$, and if so,
returns this edge. In particular, your data structure should
answer these queries in worst case $O(\log n)$ time. Briefly
analyze the preprocessing and space required.
\qpart[7] Given two points $s,t \in \R^2$, let
$P[s,t] \subseteq P$ be the maximal polyline with starting point
$s$ and ending point $t$ (and note that $P[s,t] = \emptyset$ if
$s$ or $t$ does not lie on $P$).
Describe a data structure that stores $P$ and can answer the
following queries in $O(\log^c n)$ (expected or worst case)
time, for some $c > 1$: given two query points $s,t \in \R^2$
report the axis-parallel bounding box of $P[s,t]$.
Analyze the space usage of your data structure and its
preprocessing time.
The number of points awarded for this question depends on the
query time and space usage of your data structure. Aim for the
fastest possible queries, while using subquadratic space.
\qpart[10] Describe a data structure that stores $P$ and can
answer the following queries in $O(\log^c n)$ (expected or worst
case) time, for some $c > 1$: given three points
$s,t,q \in \R^2$, report the vertex in $P[s,t]$ closest to
$q$. Analyze the space usage of your data structure and its
preprocessing time.
The number of points awarded for this question depends on the
query time and space usage of your data structure. Aim for the
fastest possible queries, while using subquadratic space.
\qpart[3] Suppose that $P$ may have self intersections. Briefly
describe why/where in your solution for question c you need that
$P$ has no self-intersections.
\end{parts}
\end{questions}
\end{document}