m4_divert(2) m4_define(_commentnesting, 0) m4_define(_begincomment,m4_dnl m4_ifelse(_commentnesting, 0, )) m4_define(_warning,m4_dnl _begincomment()This document was created by gen-_name.html Do not edit this document, edit gen-_name.html._endcomment()) m4_define(_hdrs, ) m4_define(_anchor_no, 0) m4_define(_abs, m4_ifelse(m4_eval($1 < 0), 1, m4_eval(-($1)), $1)) m4_define(hdr, _warning() $2 _warning() m4_ifelse(m4_eval($1 >= 0), 1, m4_define(`_hdrs', _hdrs`'_anchor_no $1 m4_translit(`$2', `,', ) )) m4_define(_anchor_no, m4_eval(_anchor_no + 1)) ) m4_define(usetag, _warning()$2_warning()) m4_define(puttag, _warning()$2_warning()) m4_changecom() m4_define(sps, $1$2) m4_define(sbs, $1$2) m4_define(emph,_warning()$1_warning()) m4_define(cde,_warning()$1_warning()) m4_define(itl,_warning()$1_warning()) m4_define(bld,_warning()$1_warning()) m4_define(hrf,_warning()$2_warning()) m4_define(mailat,_warning()hrf(mailto:$1,$1)_warning()) m4_define(nwsgrp, hrf(news:$1, $1)) m4_define(bookref, $1, $2. $3: $4, $5.) m4_define(i2m,m4_ifelse( $1,01,January, $1,02,February, $1,03,March, $1,04,April, $1,05,May, $1,06,June, $1,07,July, $1,08,August, $1,09,September, $1,10,October, $1,11,November,December)) m4_dnl $Revision: 1.5 $, $Date: 1999/12/09 19:16:32 $ Lecture notes for CS 512, Algorithm Design

Lecture Notes for CS 512, Algorithm Design

9-14 September 1999

These are provisional lecture notes, expect changes.

  1. geometric algorithms

    1. many cases to consider

  2. is a point inside or outside a polygon?

    1. terms - polygon, concave, convex

    2. simple idea - count boundary crossings (jordan curve theorem)

    3. complexities - vertex crossing, overlapping edges

    4. simplify the algorithm by artful choice of the vector

    5. cost is O(|V|)

  3. making simple polygons

    1. terms - simple polygon, path, closed path, simple path

    2. form a simple closed path among a set of planar points

    3. idea - sweep a circular arc through the points

      1. sweep out component triangles

      2. problem - > 180 sweeps are not convex

      3. fix - reposition the sweep point to not outside the polygon

      4. sort by angles

    4. simplify by using similar but simpler values - slopes for angles and squared distances

    5. cost is the cost of sorting - O(|V|log|V|)

  4. convex hulls

    1. concave polygon containing all points

    2. start with a convex hull and work up

      1. pick three vertices for the convex hull

      2. add a new vertex

      3. is the new vertex inside or outside the hull

      4. if inside, toss, if outside, add the vertex to the hull

      5. if a new hull, cull the previous hull points

      6. complicated, costs O(|V|^2) time

    3. start with a part of the final convex hull and build it up

      1. extremal points and circular sweeping

      2. simple, but still costs O(|V|^2) time via the sweep through the remaining points

    4. control excessive scanning by ordering the points - Graham's scan

      1. sort by angle from an extreme point

      2. trace backwards from the new point to cull existing ones

      3. because of sorting, cost is O(|V|log|V|)

  5. nearest neighbor

    1. straightforward algorithm takes O(|V|^2) time

    2. how can the problem size be reduced?

      1. divide into halves - quick reduction, pairs are easy; recombination is difficult

      2. nearest-neighbor properties make reconbination simpler - sorted strips

      3. the cost is O(|V|log^2|V|) because of the double sort

      4. the idea - start out sorted and keep it sorted; only takes O(n) to do, reducing cost to O(|V|log|V|)

  6. finding intersections

    1. all-pairs comparison takes O(mn) time

    2. organize the search in a sweep

This page last modified on 21 i2m(09) 1999. m4_dnl $Revision: 1.2 $, $Date: 1999/03/12 17:36:48 $ m4_divert(1) m4_changequote({, }) {m4_define(tblfcntnts, _toc_tableit(}_hdrs{) _toc_down(_toc_ilevel, _toc_level) ) m4_define(_toc_tableit, m4_regexp($1, \([0-9]+\) \([0-9]+\) \([^ ]+\) \(.*\), m4_ifdef(_toc_level, , m4_define(_toc_level, m4_eval(\2 - 1)) m4_define(_toc_ilevel, _toc_level)) _toc_entry(\1, \2, \3) _toc_tableit(\4)) ) m4_define(_toc_down, m4_ifelse(m4_eval($1 < $2), 1, _toc_down($1, m4_eval($2 - 1))) ) m4_define(_toc_entry, m4_ifelse(m4_eval($2 > _toc_level),1,