Polygons.bravo -- February 11, 1983 12:09 PM --- Stolfi
[ ] [[someplace define simple polygon, talk about winding number computation]]
[ ] 1. Properties of Convex Polygons
[v] comments on why convex polygons are fundamental to computational geometry
[ ] supporting lines or tangents; separating lines
[ ] a convex polygon has exactly one tangent in each direction
[ ] distance between antipodal (= opposite?) tangents
[ ] 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 set
[ ] same true for minimally apart antipodal tangents
[ ] two disjoint convex polygons P and Q; consider antipodal tangents, one to P and one to Q
[ ] 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 Q
[ ] a. disjoint convex sets have a separating line
b. even one parallel to a side of one of them (Hobby argument)
[ ] 2. Testing for point Inclusion in Convex Polygon and Detecting Convex Polygon Intersection
[ ] preliminaries on geometric model of computation; queries and preprocessing
common geometric primitives; example of testing line segments for intersection
representation for convex polygons
[ ] 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 separator
[ ] 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.
[ ] can thus do decomposition into left and right chains
[ ] caveat on models of computation: direct coordinate comparisons do not suffice for point inclusion test
[ ] caveat on star-shaped and monotone polygons
[ ] detecting polygon intersection: becomes point inclusion via the fundamental theorem
[ ] general vehicle for transforming polygon-polygon to point-polygon problems; mention also distance result
[ ] caveat on computing convolutions; linear for convex, quadratic for general polygons; give examples
[ ] gives linear algorithm for testing intersection; actually log, after linear preprocessing, for any translate of P and Q.
[ ] left and right shadows; polygon intersection equivalent to two shadow intersections
[ ] 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.
[ ] 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.
[ ] translate an "origin not in the convolution" conclusion to a separating line for the two polygons
[ ] 3. Common Tangents
[ ] Take two disjoint convex polygons and wlog rotate the plane so that their separating line is vertical
[ ] Use car language; discuss states at leftmost and rightmost points
[ ] existence of exactly two outer common tangents by intecept on separator argument
existence of exactly two inner common tangents
[ ] tangents from a point to a polygon; linear algorithm
discuss bimodality of intercept on separator
[ ] delop carefully log search algorithm for bimodal function zero crossings, or maxima and minima
apply to get log algorithm for tangents
[ ] computing the outer common tangents; **give clean linear algorithm and proof
[ ] 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 maintained
[ ] new observation that eliminates L-search
[ ] 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.
[ ] discuss leftmost car; concept of monostrofic (??) tracing. Remark that common tangent computation algorithms apply also to monostrofic tracings.
[ ] derive Jarvis’s algorithm for CH from same ideas on n cars spinning on n points.
[ ]
4. Forming the Intersection of two Convex Polygons.
[ ] intersection of convex polygons is a convex polygon.
[ ] the intersection of P and Q has at most p+q sides, and this bound is attainable.
[ ] what can we say if the sides of P and Q don’t intersect?
[ ] intersection computation via shadows:
[ ] 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.
[ ] 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.
[ ] intersection computation by polar methods:
[ ] 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.
[ ] intersection computation by tangent methods:
[ ] 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.
[ ] More on CH algorithms: comments on Jarvis, present Graham.
[ ] 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.
[ ] Lower bounds for CH. Classical Shamos sorting reduction. Linear tests don’t suffice: give full argument. Mention Yao proof for quadratic tests.
[ ] 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.