Polygons.bravo -- February 11, 1983  12:09 PM --- Stolfil3648d2999e12(635)
[ ]   [[someplace define simple polygon, talk about winding number computation]]l3648d2999e12
[ ]  1. Properties of Convex Polygonsl3648d2999e12
[v]  comments on why convex polygons are fundamental to computational geometryl3648d2999e12
[ ]  supporting lines or tangents; separating linesl3648d2999e12
[ ]  a convex polygon has exactly one tangent in each directionl3648d2999e12
[ ]  distance between antipodal (= opposite?) tangentsl3648d2999e12
[ ]  maximally apart antipodal tangents
	a. touch the polygon exactly once each
	b. line joining points of contact is perpendicular to the tangents
	c. length of that segment equals the diameter of the setl3648d3008e12
[ ]  same true for minimally apart antipodal tangentsl3648d2999e12
[ ]  two disjoint convex polygons P and Q; consider antipodal tangents, one to P and one to Ql3648d2999e12
[ ]  if (p,q) is the distance from P to Q, then the tangents at p and q are antipodal and are perpendicular to P and Ql3648d2999e12
[ ]  	a. disjoint convex sets have a separating line
	b. even one parallel to a side of one of them (Hobby argument)l3648d2999e12
[ ]  2. Testing for point Inclusion in Convex Polygon and Detecting Convex Polygon Intersectionl3648d2999e12
[ ]  preliminaries on geometric model of computation; queries and preprocessing
common geometric primitives; example of testing line segments for intersection
representation for convex polygonsl3648d2999e12
[ ]  linear algorithm for testing for point inclusion
exploiting ordering of the edges: polar algorithm
division into y-monotone chains and shadows; importance of preprocessing
** discrimination of a point against an y-monotone chain
if not in shadow, give separatorl3648d2999e12
[ ]  location of extremal vertices in a direction is the set of points where the car faces in that direction +90. Can therefore locate extremal vertex (or possibly edge) by binary search in the circle of directions.l3648d2999e12
[ ]  can thus do decomposition into left and right chainsl3648d2999e12
[ ]  caveat on models of computation: direct coordinate comparisons do not suffice for point inclusion testl3648d2999e12
[ ]  caveat on star-shaped and monotone polygonsl3648d2999e12
[ ]  detecting polygon intersection: becomes point inclusion via the fundamental theoreml3648d2999e12
[ ]  general vehicle for transforming polygon-polygon to point-polygon problems; mention also distance resultl3648d2999e12
[ ]  caveat on computing convolutions; linear for convex, quadratic for general polygons; give examplesl3648d2999e12
[ ]  gives linear algorithm for testing intersection; actually log, after linear preprocessing, for any translate of P and Q.l3648d2999e12
[ ]  left and right shadows; polygon intersection equivalent to two shadow intersectionsl3648d2999e12
[ ]  convolution of left shadows is a left shadow; remark on convolution vs. other edge interleavings and "sorting by swapping"
run point discrimination algorithm without computing convolution first, by placing each edge as you need to; must use middle edge of longest chain. Gives O(lg^2 n). Comment on generality of technique.l3648d2999e12
[ ]  O(lg n) algorithm for discrimination: use middle edges of both chains. In constant time can throw away half the edges of one or half the edges of the other. Reamrk on termination and switching strategy.l3648d2999e12
[ ]  translate an "origin not in the convolution" conclusion to a separating line for the two polygonsl3648d2999e12
[ ]  3. Common Tangentsl3648d2999e12
[ ]  Take two disjoint convex polygons and wlog rotate the plane so that their separating line is verticall3648d2999e12
[ ]  Use car language; discuss states at leftmost and rightmost pointsl3648d2999e12
[ ]  existence of exactly two outer common tangents by intecept on separator argument
existence of exactly two inner common tangentsl3648d2999e12
[ ]  tangents from a point to a polygon; linear algorithm
discuss bimodality of intercept on separatorl3648d2999e12
[ ]  delop carefully log search algorithm for bimodal function zero crossings, or maxima and minima
apply to get log algorithm for tangentsl3648d2999e12
[ ]  computing the outer common tangents; **give clean linear algorithm and proofl3648d2999e12
[ ]  give log^2 algorithm based on separator intercept
give log algorithm based on predicates
	RA: A is to the right of b
	RB: B is to the right of a
	and cutting up the product space
discuss L-shape binary search in detail with invariants maintainedl3648d2999e12
[ ]  new observation that eliminates L-searchl3648d2999e12
[ ]  remark on always following rightmost car; prove that when we switch from one tracing to the next, the car moves forwards. Thus result is a convex tracing, the convex hull.l3648d2999e12
[ ]  discuss leftmost car; concept of monostrofic (??) tracing. Remark that common tangent computation algorithms apply also to monostrofic tracings.l3648d2999e12
[ ]  derive Jarvis's algorithm for CH from same ideas on n cars spinning on n points.l3648d2999e12
[ ]  
4. Forming the Intersection of two Convex Polygons.l3648d2999e12
[ ]  intersection of convex polygons is a convex polygon.l3648d2999e12
[ ]  the intersection of P and Q has at most p+q sides, and this bound is attainable.l3648d2999e12
[ ]  what can we say if the sides of P and Q don't intersect?l3648d2999e12
[ ]  intersection computation via shadows:l3648d2999e12
[ ]  computing the intersection of two left shadows. Algorithm that works for any two y-monotone chains: consider merging the two y-ordered lists of vertices; as we advance along one list, we check for intersection with edge coming out of current position on the other list. Claim: this detects all crossings and obviously runs in linear time.l3648d2999e12
[ ]  computing the intersection of a left and right shadow. Show that if there is an interior point to the intersection, then the edge chains intersect at exactly two points. We can find these two points either by previous method, or by a log search.l3648d2999e12
[ ]  intersection computation by polar methods:l3648d2999e12
[ ]  if we know an intersection point, then we can rotate a ray around it and stay with the innermost car. Comment on doing this from an arbitrary point.l3648d2999e12
[ ]  intersection computation by tangent methods:l3648d2999e12
[ ]  Car pairings that lead to intersection finding. Above cartesian and polar methods require special features. Present "Alice sees Bob" pairing. "Aims" predicate and advancing rules. Algorithm based on those. Definition of being in phase: one car on inner tracing, the other to its right. Rules will get the cars in phase from any starting position. Once in phase, they will meet at the next intersection point and still be in phase.l3648d2999e12
[ ]  More on CH algorithms: comments on Jarvis, present Graham.l3648d2999e12
[ ]  Kirkpatrick's O(n lgh) method. Testing the validity of an alleged convex hull. Finding the common tangents of two separated point sets in linear time. Recursive call with point set and interval. Accounting. l3648d2999e12
[ ]  Lower bounds for CH. Classical Shamos sorting reduction. Linear tests don't suffice: give full argument. Mention Yao proof for quadratic tests.l3648d2999e12
[ ]  Brief excursion into 3 dimensions. Mention definition of tracings in 3-d. Notions of polyhedra. Euler's relation and Cauchy's proof of it (for simple polyhedra with simple faces). Linearity between vertices, edges, and faces in 3-d polyhedra. Intuitive discussion of the Preparata-Hong CH algorithm in 3-d.l3648d2999e12
l3648d2999e12
l3648d2999e12