Introduction to Computational Geometry: Line Arrangements and Discrepancy Problems

Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Line Arrangements Outline: I. Geometric complexity of a line arrangement II. Incremental construction III. Computation of the discrete discrepancy measure Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.

The Discrepancy Problem ?( ) =1 Point Continuous measure: 4 ??( ) =3 Discrete measure: 8 Maximize |??( ) ?( )| must have 1 points on its boundary. ?(?2) exactly one point (Type i) brute-force method at least two points (Type ii) apply duality + line arrangement

I. Arrangement of Lines Point ?: a set of ? lines. ?(?): planar subdivision induced by ?. with unbounded edges and faces Simple arrangement if no three lines are concurrent; face no two lines are parallel. vertex

Reduction to Line Arrangment Point Problem on points problem on an arrangement of dual lines. ? ? ? ? ? ? dual plane primal plane Structure of a line arrangement is more apparent than that of a point set.

Combinatorial Complexity #vertices + #edges + #faces Point Theorem #vertices ?(? 1) 2 #edges ?2 #faces ?2 2+? 2+ 1 Equality holds if and only if ?(?) is simple.

Proof of Complexity We first show that #vertices, #edges, #faces are maximal when ?(?) is simple (no parallel or 3 concurrent lines) and not otherwise. Point 1) Let ? ? be parallel to one or more lines. small enough rotation to yield new vertex ? ? one change in ?(?) ?1 ?1 Complexity increases in this case. (Hence such configuration cannot be maximal.)

Proof (Contd) 2) Suppose ? passes through a vertex. Point ?1 ?1 ? ? translate ? slightly ?2 ?2 2 new vertices 3 new edges 1 new face Since complexity increases, such configuration cannot be maximal either. The arrangement with maximal complexity must be simple.

Exact Size of a Simple Arrangement ??= # vertices Point ??= ??= # edges # faces ? 2 =?(? 1) Any pair of lines intersect. ??= 2 ? #edges on one line = 1 + #intersections on the line ? 1 ??= ? (1 + ? 1) = ?2

Number of Faces 1. Add a vertex ? at infinity. Point ? 2. Extend (and bend) every half-infinite edge to ? . No edge crossing Planar graph Euler s formula: ??= 2 (??+ 1) + ?? (??+ 1) + ?? ??= 2 ?(? 1) 2 + 1 + ?2 = 2 =?2 2+? 2+ 1

II. Storage of Line Arrangement Doubly-connected edge list. Point Add a bounding box to contain all vertices in interior.

Construction of DCEL for ?(?) Point Plane sweep? ?(?log? + ?log?) = ?(?2log?) pairwise intersection ? = ?(? 1)/2 Not optimal!

Incremental Algorithm Preprocessing Point (?2) Compute the bounding box ?(?). ?(? 1)/2 intersections. leftmost, rightmost, top, bottom intersections. each line yielding two intersections with ?(?). + 2? + 4 =?2+3?+8 ? ? 1 vertices in ?(?). 2 2 Add lines ?1,?2,...,?? one by one. Update the DCEL after each addition.

Updating the Subdivision ??: subdivision due to {?1,?2,...,??} Point Case 1 Enter a face ? through edge ?. ?? ? ? - Walk along boundary of ? using the the Next pointer. ? ? - Find exit edge ? . - Use its Twin() pointer to enter face ?. ?? 1

Updating the Subdivision Case 2 Leave a face (?) through a vertex (?). Point - walk around ? to find the next face ( ) intersected by ??. ?? ? Alternatively use Next() and Twin() pointers.

First Edge of Intersection How to find the first edge (leftmost edge) intersected by ??? Point It must be an edge on the bounding box ?(?). ?? ? Just test all the edges on ?(?). In case ?? is vertical, locate the bottom intersection to start off traversal. ?? 1has 2(? 1) + 4 edges on ?(?) since each edge intersects it twice. First intersection edge can be found in ?(?) time.

Splitting a Face Point ?? 2 new faces 1 new vertex 6 new half-edges ? edge already split when exiting new ?1 vertex ?? ?2

The Algorithm ConstructArrangement(?) Point ?(?2) Compute a bounding box ?(?) to contain all vertices of ?(?)// Initialize DCEL for ?(?) // ?(1) for? 1 to ? do ? edge on ?(?) that first intersects with ?? ? bounded face incident on ? while ? is bounded split ? ? next intersected face 1. 2. 3. 4. 5. 6. 7. 8. // ?(?)

Face Splitting Split faces in ?? 1 intersected by ??. Point ?(?) simple Splitting a face ? and finding the next intersected face ?(complexity of ?) complexity? Total Insertion of ?? takes time linear in total complexity of faces intersected by the line. ?(?) not simple ?? ?? may leave ?through a vertex ? where 3 lines including ?? intersect. ? Walk around ? to find the next face (?) to split, scanning over edges that bound faces intersected by ??. ? ?

Zone ?(?) = { ? | ? is a face of ?(?) intersected by ? } Point ?1 (counted once) ?3 (three times) ? Complexity of ? = total complexity of faces (#vertices + #edges). A vertex may be counted 4 times.

Time of Arrangement Construction Zone Theorem Complexity of zone in an arrangement of ? lines is ?(?). ProofBy induction. Point Thus, insertion of one line takes ?(?) time. Time to insert all lines, and thus to construct line arrangement: ? ?(?) = ?(?2) ?=1

III. Discrete Measure Primal plane Dual plane Point ? ? ?(?,?) ?(?,?) ? ? points below ?(?,?) lines strictly above dual point ?(?,?) Efficient algorithm exists!

How to Use Duality? A set ? of ? sample points Point A set ? of ? (dual) lines A line through 2 sample points A vertex in the arrangement ?(? ) Because? lies above ? iff ? lies above ? , the discrepancy problem reduces to the following: ProblemFor every vertex in ?(? ), compute the numbers of lines above it, passing through it, and below it.

Reduction ??= # lines above a vertex ??= # lines below the vertex ??= # lines through the vertex Point Sufficient to compute 2 of 3 numbers (with sum ?). ??is known from DCEL. Need only compute ?? of every vertex in ?(? ).

Levels of Vertices in an Arrangement level of a point = # lines strictly above it. A line ? is above a point ? if its intersection with the vertical line through ? is above ?. Point ?6 0 ?5 ?1 1 1 2 2 ?2 ?4 ?3 2 3 3 3 ?4 ?3 4 3 ?2 ?1

Counting Levels of Vertices ?5 ?4 ?3 ?2 For each line?, compute the levels of vertices on it. ?1 ? ?1,?2,...,?? 1 intersections with ? 1 other lines Strategy: walk along ? from left to right.

Counting Levels of Vertices ?4 ?3 ?1 2 no change of level between vertices 2 ?2 Point 1 ?4 3 ?5 1 level(?1) determined in ?(?) time by checking how many of the ? 1 remaining lines are above ?1. 0 ?3 0 ?5 0 1 1 ?2 + ?1 ?1 ? level(?1) if the line crossing ?1 comes from above level ?1 + 1 if the crossing line comes from below +)= level(?1 +: a point in ?? the interior of ????+1 A line crossing ??, ? > 1, is coming coming from above a) from above +) 1 level(??)= level(?? 1 coming from below += level(??) level ?? b) from below +) level(??) = level(?? 1 +) = level(??) + 1 level(??

Running Times Levels of vertices along a line computable in ?(?) time. Point Levels of all vertices in a line arrangement can be computed in ?(?2) time.

Discrete Measures & Degeneracy Discrete measures of all type ii) half-planes are computable in ?(?2) time if no two points are on the same vertical line. Point What if two or more points are on the same vertical line ?? ? undefined and thus does not show up as an intersection in the dual plane. For every vertical line through 2 points, determine the discrete measure of the corresponding half-plane. Only ?(?) such vertical lines. Their discrete measures can be computed in ?(?2) time.

Summary Maximum discrepancy due to half-planes: Point max ?( ) = |? ?? | The boundary line of the maximizing must pass either i) one point or ii) 2 points. Discrepancies of the ? type i) candidates for can be computed in ? ?2 time by using calculus to find extrema of the continuous measure ? . (Discrete measure each takes time ? ? .) For ? ?2type ii) candidates, effort is on the discrete measure ?? . Deal with all vertical lines passing through 2 points (? ?2). Use duality to compute ?? for all the non-vertical lines through 2 points (? ?2). Total time: ? ?2