\documentclass{article}
\usepackage{xspace}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{ifthen}
\usepackage{totcount}
\usepackage{algpseudocode}
\usepackage[usenames]{xcolor}
\usepackage[most]{tcolorbox}
\usepackage[a4paper, margin=1in]{geometry}

\graphicspath{ {./figures/} }

%--------------------------------------------------------------------------------

\newcommand{\edition}{2025-2026}
\newcommand{\deadline}{10 December 2025}
\newcommand{\hwNum}{2}

\newcommand{\student}{\color{red} My name and StudentID go here!}

%--------------------------------------------------------------------------------
% Style stuff
\pagestyle{fancy}
\lhead{Geometric Algorithms (INFOGA \edition)}
\chead{}
\rhead{\mytitle}
\lfoot{INFOGA \edition}
\cfoot{\student}
\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{question}[1][0]{\begin{tcolorbox}[parbox=false
                                      ,breakable=true
                                      ,enhanced jigsaw
                                      ,title=\bfseries Question
                                      \stepcounter{questionscounter}\arabic{questionscounter}
                                      \withpoints{#1}]
                         }
                         {\end{tcolorbox}}
\newenvironment{subquestions}{\begin{enumerate}[leftmargin=*
                                        ]}
                             {\end{enumerate}}
\newcommand{\subquestion}[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}
\DeclareMathOperator{\argmax}{argmax}

\newcommand{\mkmbb}[1]{\ensuremath{\mathbb{#1}}\xspace}
\newcommand{\R}{\mkmbb{R}}

\newcommand{\mathfunc}[1]{\ensuremath{\mathit{#1}}\xspace}

\newcommand{\CH}{\ensuremath{\mathit{CH}}\xspace}

%--------------------------------------------------------------------------------
% The Actual document

\newcommand{\mytitle}{Homework Exam \hwNum\xspace\edition}
\title{\mytitle}
\date{\textbf{Deadline: } \deadline}
\author{\student}


\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{question}[20] Let $\mathcal{S}$ be a planar subdivision with
    $n$ vertices, represented as a DCEL. Give \emph{pseudo-code} for
    an output sensitive algorithm that, given a pointer to a face $F$,
    reports all $k$ half-edges that have a vertex in common with $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 and analyze its running time.
  \end{question}


  \begin{question}
    \begin{subquestions}
      \subquestion[10] Show that a triangulation of a polygon with
      $n \geq 9$ vertices with $h > 1$ holes may consist of more than $n$
      triangles. That is, describe a construction that, given a number
      $n \geq 9$, constructs a polygon $P_n$ with $n$ vertices that
      has a triangulation with more than $n$ triangles.

      \subquestion[15] Prove that any triangulation of a polygon $P$
      with $n$ vertices and $h$ holes actually has the same number of
      triangles.
    \end{subquestions}
  \end{question}

  \begin{question}
    Let $p \in \R^2$ be a point, and let $S$ be a set of $n$ disjoint
    line segments in the plane. You may assume that the set containing
    $p$ and all endpoints of the segments in $S$ has no three colinear
    points (and thus $p$ does not lie on any of the segments).

    \begin{subquestions}
      \subquestion[20] Develop an algorithm to compute the length of a
      longest line segment $\overline{pq}$ that does not properly
      intersect the interior of any segment in $S$. (Recall that two
      segments properly intersect if and only if their interiors
      intersect). If segment $\overline{pq}$ does not exist your
      algorithm should return $\infty$. Prove that your algorithm is
      correct and analyze its running time.

      Note: the number of points rewarded for this question will
      depend on the running time of your algorithm.

      \subquestion[5] Is your algorithm still correct if the segments
      in $S$ may intersect? If so, argue why, if not, give an example
      why not, and describe how to fix it. You do \emph{not} have to
      argue about the running time of your algorithm in this scenario.
    \end{subquestions}

  \end{question}

  \begin{question}[20]
    Let $P$ be a set of $n$ points in $\R^2$, let $z$ be a point that
    lies strictly in the interior of the convex hull $\CH(P)$, and let
    $\rho$ be a ray (oriented half-line) that starts in $z$. Develop
    an expected $O(n)$ time algorithm that, given $P$, $z$, and
    $\rho$, can find the edge of $\mathit{CH}(P)$ hit by $\rho$. Prove
    that your algorithm is correct and achieves the desired running
    time. You may assume that no three points in $P$ are colinear, and
    that $\rho$ contains no points of $P$.

    Note that you are \emph{not} given $\CH(P)$ itself.
  \end{question}

\end{document}
