Chapter_33_Computational_Geometry/exercises_33.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 33.2 Determining whether any pair of segments intersects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-1\n",
    "\n",
    "> Show that a set of $n$ line segments may contain $\\Theta(n ^ 2)$ intersections."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Star."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-2\n",
    "\n",
    "> Given two segments $a$ and $b$ that are comparable at $x$, show how to determine in $O(1)$ time which of $a \\succeq_x b$ or $b \\succeq_x a$ holds. Assume that neither segment is vertical. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $a = \\overline{(x_1, y_1)(x_2, y_2)}$ and $b = \\overline{(x_3, y_3)(x_4, y_4)}$,\n",
    "\n",
    "$$\n",
    "\\frac{x - x_1}{x_2 - x_1} = \\frac{y - y_1}{y_2 - y_1}\n",
    "$$\n",
    "\n",
    "$$\n",
    "y = (x - x_1) \\cdot \\frac{y_2 - y_1}{x_2 - x_1} + y_1\n",
    "$$\n",
    "\n",
    "$$\n",
    "y' = (x - x_3) \\cdot \\frac{y_4 - y_3}{x_4 - x_3} + y_3\n",
    "$$\n",
    "\n",
    "Compare $y$ and $y'$. To avoid division, compare $(x_2 - x_1) \\cdot y$ and $(x_4 - x_3) \\cdot y'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-3\n",
    "\n",
    "> Professor Mason suggests that we modify ANY-SEGMENTS-INTERSECT so that instead of returning upon finding an intersection, it prints the segments that intersect and continues on to the next iteration of the __for__ loop. The professor calls the resulting procedure PRINT-INTERSECTING-SEGMENTS and claims that it prints all intersections, from left to right, as they occur in the set of line segments. Professor Dixon disagrees, claiming that Professor Mason's idea is incorrect. Which professor is right? Will PRINT-INTERSECTING-SEGMENTS always find the leftmost intersection first? Will it always find all the intersections?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No.\n",
    "\n",
    "No."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-4\n",
    "\n",
    "> Give an $O(n \\lg n)$-time algorithm to determine whether an n-vertex polygon is simple."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same as ANY-SEGMENTS-INTERSECT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-5\n",
    "\n",
    "> Give an $O(n \\lg n)$-time algorithm to determine whether two simple polygons with a total of $n$ vertices intersect."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same as ANY-SEGMENTS-INTERSECT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-6\n",
    "\n",
    "> A __*disk*__ consists of a circle plus its interior and is represented by its center point and radius. Two disks intersect if they have any point in common. Give an $O(n \\lg n)$- time algorithm to determine whether any two disks in a set of $n$ intersect."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same as ANY-SEGMENTS-INTERSECT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-7\n",
    "\n",
    "> Given a set of $n$ line segments containing a total of $k$ intersections, show how to output all $k$ intersections in $O((n + k) \\lg)$ time.\n",
    "\n",
    "Treat the intersection points as event points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-8\n",
    "\n",
    "> Argue that ANY-SEGMENTS-INTERSECT works correctly even if three or more segments intersect at the same point."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 33.2-9\n",
    "\n",
    "> Show that ANY-SEGMENTS-INTERSECT works correctly in the presence of vertical segments if we treat the bottom endpoint of a vertical segment as if it were a left endpoint and the top endpoint as if it were a right endpoint. How does your answer to Exercise 33.2-2 change if we allow vertical segments?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}