#LyX 1.3 created this file. For more info see http://www.lyx.org/ \lyxformat 221 \textclass amsart-seq \language english \inputencoding auto \fontscheme default \graphics default \paperfontsize default \spacing single \papersize a4paper \paperpackage widemarginsa4 \use_geometry 0 \use_amsmath 1 \use_natbib 0 \use_numerical_citations 0 \paperorientation portrait \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \defskip medskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 1 \paperpagestyle default \layout Standard \begin_inset FormulaMacro \newcommand{\li}[2]{\lim_{#1\rightarrow#2}} \end_inset \begin_inset FormulaMacro \newcommand{\lii}[1]{\li{#1}{\infty}} \end_inset \begin_inset FormulaMacro \newcommand{\lixi}{\lii{x}} \end_inset \begin_inset FormulaMacro \newcommand{\lini}{\lii{n}} \end_inset \begin_inset FormulaMacro \newcommand{\lixz}{\li{x}{0}} \end_inset \begin_inset FormulaMacro \newcommand{\linz}{\li{n}{0}} \end_inset \begin_inset FormulaMacro \newcommand{\eps}{\varepsilon} \end_inset \begin_inset FormulaMacro \newcommand{\vphi}{\varphi} \end_inset \begin_inset FormulaMacro \newcommand{\imp}{\Rightarrow} \end_inset \begin_inset FormulaMacro \newcommand{\Rarr}{\Rightarrow} \end_inset \begin_inset FormulaMacro \newcommand{\ToDo}[1]{\mathbf{\left[ToDo:#1\right]}} \end_inset \begin_inset FormulaMacro \newcommand{\todo}[1]{\ToDo{#1}} \end_inset \begin_inset FormulaMacro \newcommand{\iab}[1]{\int_{a}^{b}#1dx} \end_inset \begin_inset FormulaMacro \newcommand{\ab}{\left[a,b\right]} \end_inset \begin_inset FormulaMacro \newcommand{\df}{\triangleq} \end_inset \begin_inset FormulaMacro \newcommand{\dto}{\twoheadrightarrow} \end_inset \begin_inset FormulaMacro \newcommand{\ser}[1]{\sum_{n=#1}^{\infty}} \end_inset \begin_inset FormulaMacro \newcommand{\rn}{\mathbb{R}^{n}} \end_inset \begin_inset FormulaMacro \newcommand{\norm}[1]{\left\Vert #1\right\Vert } \end_inset \begin_inset FormulaMacro \newcommand{\diam}{\textrm{diam}} \end_inset \begin_inset FormulaMacro \newcommand{\R}{\mathbb{R}} \end_inset \begin_inset FormulaMacro \newcommand{\C}{\mathbb{C}} \end_inset \begin_inset FormulaMacro \newcommand{\N}{\mathbb{N}} \end_inset \begin_inset FormulaMacro \newcommand{\Z}{\mathbb{Z}} \end_inset \begin_inset FormulaMacro \newcommand{\xto}[2]{\xrightarrow[#2]{#1}} \end_inset \begin_inset FormulaMacro \newcommand{\mb}[1]{\mathbb{#1}} \end_inset \begin_inset FormulaMacro \newcommand{\es}{\emptyset} \end_inset \begin_inset FormulaMacro \newcommand{\modeq}[3]{#1\equiv#2\textrm{ (mod }#3\textrm{ )}} \end_inset \begin_inset FormulaMacro \newcommand{\ol}[1]{\overline{#1}} \end_inset \begin_inset FormulaMacro \newcommand{\fto}{\leftrightarrow} \end_inset \begin_inset FormulaMacro \newcommand{\e}{\eps} \end_inset \begin_inset FormulaMacro \newcommand{\al}{\alpha} \end_inset \begin_inset FormulaMacro \newcommand{\la}{\lambda} \end_inset \begin_inset FormulaMacro \newcommand{\0}{\omega} \end_inset \begin_inset FormulaMacro \newcommand{\nsg}{\triangleleft} \end_inset \layout Author Daniel Vainsencher 015516180 \layout Title Applied geometry \layout Date 11/3/2005 \layout Section admin \layout Standard Freddy Brookshtein 718, 4361 (or Yana at 4898 for a meeting) freddy@cs \layout Standard Reception hours after class \layout Standard Assistant Elli Oshrovitz oeli@cs \layout Standard Grade around challanges in some general way \layout Section Intro - interesting prolblems \layout Standard Challenge - alternate proof to impossibility of tiling a lacking chess board with dominoes \layout Standard Proof that any tiling of a hexagon (with the three parallelogram) fits some arrangement of cubes. \layout Section Points and lines in the plane \layout Standard Points placed randomly will usually be in general position (no three on a line) \layout Standard non-general position: every two points have another one on the line. Is it possible for them not to be on a line? \layout Theorem Sylvester Galai Erdosh No. \layout Proof Beautiful proof based on minimal non-zero distance from point to a line, finding a smaller one, distance-less proofs exist. \layout Definition Arbitrary position - everything in between. \layout Subsection Separability \layout Standard Convex Hull the intersection of all convex sets that \layout Theorem Convex sets are the convex combinations of the extremal point (Klein Milman) \layout Remark A deep theorem and requires proof, not as trivial as it seems. \layout Definition Two sets are linearly separable iff their convex hulls are disjoint \begin_deeper \layout Definition The points are linearly separable by line \begin_inset Formula $A$ \end_inset , iff the projections of the points onto a perpendicular line are separated by a point on that line. Can be formalized with scalar products \end_deeper \layout Definition How many dichotomies (partitions into two sets) are linearly separable? \layout Theorem For the general arrangements, this is independent of the arrangement. \layout Proof Sketch - add 1 to the points in \begin_inset Formula $z$ \end_inset . All linear separations can be expressed as inner products with 3d unit vectors. Each point that needs to be classified induces an equivalence relation on the sphere with two classes, divided by a great circle. Then the number of possible distinct separations is the number of cones into which space is devided the planes through those great circles. This is \begin_inset Formula $LS\left(n+1\right)=LS\left(n\right)+2n\iff LS\left(n\right)=2+n\left(n-1\right)$ \end_inset \layout Problem What about non-general positions? \layout Standard We define \begin_inset Formula $p_{i}p_{j}$ \end_inset to be an adjacent pair if on the line through them, there is no point between them. \layout Exercise number of linearly separable subsets of a scattering is the number of ordered adjacent pairs + 2 \layout Proof Two proofs - one through the link to planes in 3space, the other on the plane, start from the lines between the pair, and perturb it either clockwise or anti clockwise, creating a separation. Then show that no two pairs can create the same separation. \layout Subsection Link to convex hulls \layout Standard \begin_inset Formula $LS\sim CH\left(red\right)\cap CH\left(blue\right)$ \end_inset . Then in an extremal separation, there is a line between two points each from a set, and there is no point between them (though there may be more points from the hulls later). \layout Remark A computer screen is like \begin_inset Formula $\Z_{1000}^{2}$ \end_inset . How many linear separations are there of the screen? \layout Remark \begin_inset Formula $\left(i,j\right)$ \end_inset is an adjacent pair of \begin_inset Formula $\left(k,l\right)$ \end_inset iff \begin_inset Formula $gcd\left(k-i,l-j\right)=1$ \end_inset . Then how many of the pairs are such? about \begin_inset Formula $5/\pi^{2}N^{4}+O\left(\textrm{lower orders}\right)$ \end_inset . Proof of this in Alfred's paper \begin_inset Quotes eld \end_inset the number of digital straight lines on an \begin_inset Formula $n$ \end_inset by \begin_inset Formula $n$ \end_inset grid \begin_inset Quotes erd \end_inset . \layout Subsection Line - Point duality \layout Standard We can look at a point as the set of possible lines ( \begin_inset Quotes eld \end_inset pencil \begin_inset Quotes erd \end_inset of lines) that intersect in it. Each point pass in dual (Hugh) space through \begin_inset Formula $\left(0,y\right)$ \end_inset and \begin_inset Formula $\left(y/x,0\right)$ \end_inset . \layout Standard Given lots of points on the screen, some of which are parts of a straight line. Which are they? take the lines representing all those points, then the pixel through which lots of lines pass intersection is dual point, which is the line we are looking for. \layout Standard Take points, move them to lines in the dual, then the regions are related to the linearly separable sets. How exactly? \layout Subsection There are other parametrizations of lines \layout Standard I'm missing the \begin_inset Formula $\rho\theta$ \end_inset parametrization here... \layout Subsection More on Convex Hulls \layout Standard \begin_inset Formula $CH\left\{ p_{1}\dots p_{n}\right\} =\bigcap_{S}\left\{ p_{1},\dots,p_{n}\right\} \subset S\textrm{ is convex}$ \end_inset . \layout Definition The extremal points are those that cannot be represented as a convex combination of the other points. \layout Theorem A compact convex set in \begin_inset Formula $S\subset\R^{2}$ \end_inset is the convex hull of the extremal points. \layout Theorem The convex hull can be triangulated, and any point that is not extremal is a convex combination of only the three end points of the triangle it is in. \layout Subsection Separation results \layout Standard Let \begin_inset Formula $S_{1},S_{2}$ \end_inset be two disjoint compact and convex sets in \begin_inset Formula $\R^{2}$ \end_inset , then there are two points one from each, with minimal distance. Then the convexes are separated by a perpendicular to that line? \layout Subsection Triangulation \layout Definition A triangulation is a maximal planar graph with edges inside the shape. \layout Exercise All finite regions defined by a triangulation are triangles, all edges of the convex hull are in the triangulations. \layout Subsection Eulers formula \layout Standard \begin_inset Formula $n$ \end_inset nodes in a graph \layout Standard \begin_inset Formula $e$ \end_inset edges \layout Standard \begin_inset Formula $f$ \end_inset faces (including \begin_inset Quotes eld \end_inset the rest of the plane \begin_inset Quotes erd \end_inset ) \layout Standard then \begin_inset Formula $n+f=e+2$ \end_inset . \layout Conclusion Given the number of points and the number of points are extremal, we know how many triangles in any triangulation. \layout Theorem \begin_inset Formula $n$ \end_inset points in general position, triangulated. \layout Theorem Then \begin_inset Formula $3\left(f-1\right)=2e-h$ \end_inset where \begin_inset Formula $h$ \end_inset is the number of edges in the convex hull. Applying Euler, we get \begin_inset Formula $f=2n-h-1$ \end_inset and \begin_inset Formula $e=3n-h-3$ \end_inset . Then the number of edges and faces is independent of the triangulation. \layout Theorem* We can get from any triangulation to any other by local changes. \layout Theorem* We look at the 4 nodes of 2 adjacent triangles, and remove the common edge, and replace it with the other inner edge. \layout Theorem* We define as neighbour triangulations to be such that the differ by one flip. Then we need to prove that the graph is connected. \layout Theorem* Why is this important? \layout Example Scattered data interpolations \layout Standard \begin_inset Formula $n$ \end_inset sample points in a plane, say \begin_inset Formula $z$ \end_inset is the level of air pollution. What is the expected pollution at an unsampled point? try to pass some function through them all. One simple way - triangulate them, then interpolate points based on the three points defining its triangle. But what triangulation is best? one criteria is looking for the triangulation leading to least area in 3d. A more natural criteria is that the angles should be close to 60. Then given a criteria, how do we find the maximum? simulated annealing sounds good. \layout Definition Voronoi regions - split the plane according to a set of points, according to the closest point. \layout Definition Delonay triangulation - start from a voroni tessalation, then connect the neighbouring points, you get a triangulation with good angles, and every triangle defines a circle that has no other points in it. \layout Theorem The distance between two triangulations depends on the number of crossings \layout Standard has ugly proofs.. \layout Subsection Simple polygons in the region \layout Standard Given a sequence of points, then the closed path through them doesn\i \'{t} cross itself. \layout Problem Given \begin_inset Formula $n$ \end_inset points in the plane, does such a path exist? \begin_deeper \layout Problem How many simple polygons are there? how do we search this space? \end_deeper \layout Problem Courant and Robbins prove that simple closed polygons create a division into two domains. \layout Problem How to check whether we're inside or outside? \layout Problem infinite ray: is the number of crossings even? then its outside, or turning angles (if the sum of angles taken by points along the curve comes to 360, we're inside), is the connected component of finite or infinite area? \layout Theorem Every simple polygon has at least two non overlapping EARs \layout Proof Useful fact - Every simple polygonal has an inner segment that divides it into two simple polygons of fewer points. Proof in the slides. \layout Claim From this we see that every simple polygon can be triangulated. \begin_deeper \layout Claim Also if we insert \begin_inset Formula $m$ \end_inset inner points \end_deeper \layout Claim And the number of triangles in such a triangulation is \begin_inset Formula $n+2m-2$ \end_inset \layout Subsection The integer grid \layout Standard \begin_inset Formula $\Z^{2}$ \end_inset is generated by integer combinations of a basis with two vectors. If two vectors define a triangle that has no other points, then they also form a basis. \layout Standard What other properties do \begin_inset Formula $u,v$ \end_inset have to generate the basis? \layout Theorem \begin_inset Formula $\left\{ au+bv|a,b\in\Z\right\} \equiv\Z^{2}$ \end_inset iff \begin_inset Formula $det\left[u,v\right]=\pm1$ \end_inset \begin_deeper \layout Theorem Any elementary triangle - triangle with vertices at grid points and no vertices from grid in it: \end_deeper \layout Enumerate Have area 1/2 \layout Enumerate define a basis \layout Theorem Pick's theorem \layout Theorem If P is a simple planar polygon with all vertices at lattice points and it has \begin_inset Formula $B$ \end_inset lattcie points at the border and \begin_inset Formula $I$ \end_inset lattice points inside, then \begin_inset Formula $area\left(P\right)=I+\frac{B}{2}-1$ \end_inset \layout Proof From the book - applying theorem of number of triangles in a triangulation of a simple polygon, and since all inner points are included, each triangle is of area 0.5. \the_end