Ch.1: Introduction

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 1.1. An Example: Convex Hulls 1.2. Degeneracies and Robustness 1.3. Application Domains 1.4. Notes and Comments

61 flashcards · Mathematics · by lakesare

Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses

[Computational Geometry: Introduction] You want a campus map that tells you, wherever you stand, which public phone is nearest. Which geometric structure is this map?
The Voronoi diagram of the phones: a subdivision into one region per phone, containing the points for which that phone is the nearest. Also used to model trading areas of cities, to guide robots, and to simulate the growth of crystals.
[Computational Geometry: Introduction] What is the motion planning problem?
Given a collection of geometric obstacles, find a short connection between two points that avoids collisions with the obstacles. Of crucial importance in robotics.
[Computational Geometry: Introduction] What does it mean to overlay two maps (e.g. one of the campus buildings, one of the roads)?
To combine the information of the two maps into one. One of the basic operations of geographic information systems: it involves locating objects of one map in the other, computing intersections of features, and so on.
[Computational Geometry: Introduction] How does the book define the field of computational geometry?
The systematic study of algorithms and data structures for geometric objects, with a focus on exact algorithms that are asymptotically fast. The field emerged in the 1970s.
[An Example: Convex Hulls] According to the book, good solutions to geometric algorithmic problems are based on which two ingredients?
A thorough understanding of the geometric properties of the problem, and a proper application of algorithmic techniques and data structures.
[An Example: Convex Hulls] When is a subset SSS of the plane convex?
When for every pair of points p,q∈Sp, q \in Sp,q∈S the line segment pq‾\overline{pq}pq is completely contained in SSS .
[An Example: Convex Hulls] What is the convex hull CH(S)\mathcal{CH}(S)CH(S) of a set SSS in the plane?
The smallest convex set that contains SSS , i.e. the intersection of all convex sets that contain SSS .
[An Example: Convex Hulls] For a finite set PPP of points in the plane, what is CH(P)\mathcal{CH}(P)CH(P) (the convex hull) in terms of polygons?
The unique convex polygon whose vertices are points of PPP and that contains all points of PPP . Thought experiment: the points are nails sticking out of the plane, and a rubber band released around them snaps to CH(P)\mathcal{CH}(P)CH(P) .
[An Example: Convex Hulls] P={p1,…,pn}P = \{p_1, \dots, p_n\}P={p1,…,pn} is a set of points in the plane. What exactly should an algorithm that "computes the convex hull" of PPP output?
The points of PPP that are vertices of CH(P)\mathcal{CH}(P)CH(P) , listed in clockwise order (starting with an arbitrary one).
[An Example: Convex Hulls] PPP is a finite set of points in the plane with no three on a line, and p,q∈Pp, q \in Pp,q∈P . When is pq‾\overline{pq}pq an edge of CH(P)\mathcal{CH}(P)CH(P) (the convex hull)?
If and only if all points of P∖{p,q}P \setminus \{p, q\}P∖{p,q} lie to the right of the directed line through ppp and qqq (for one of the two directions). Directing each hull edge so that CH(P)\mathcal{CH}(P)CH(P) lies to its right makes the edges run clockwise.
[An Example: Convex Hulls] PPP is a set of nnn points in the plane; pq‾\overline{pq}pq is an edge of CH(P)\mathcal{CH}(P)CH(P) if and only if all other points of PPP lie to the right of the directed line through ppp and qqq .What does the brute-force algorithm SlowConvexHull do to find the hull edges?
For every ordered pair (p,q)(p, q)(p,q) with p≠qp \ne qp=q , test every other r∈Pr \in Pr∈P ; if no rrr lies to the left of the directed line from ppp to qqq , add the directed edge pqundefined\overrightarrow{pq}pq to a set EEE . Afterwards, the edges in EEE are chained into the clockwise list of hull vertices.
[An Example: Convex Hulls] Which primitive operation do convex hull algorithms (and most geometric algorithms) need, and what does the book assume about such operations?
Testing whether a point lies to the left or to the right of a directed line. The book assumes such primitives are available and take constant time. So they don't affect the asymptotic running time; still, they are not easy to implement correctly, and their implementation affects the actual running time.
[An Example: Convex Hulls] EEE is the set of edges of a convex hull, each directed so that the hull lies to its right. How do you turn EEE into the clockwise list L\mathcal{L}L of hull vertices?
Remove any edge e⃗1\vec e_1e1 and put its origin and then its destination into L\mathcal{L}L ; then repeatedly remove the edge whose origin is the last point of L\mathcal{L}L and append its destination, until one edge is left. The destination of the last edge is the origin of e⃗1\vec e_1e1 , already the first point of L\mathcal{L}L . Simple implementation: O(n2)O(n^2)O(n2) time; can be improved to O(nlog⁡n)O(n \log n)O(nlogn) .
[An Example: Convex Hulls] SlowConvexHull: for every ordered pair (p,q)(p, q)(p,q) of distinct points of PPP , test whether all other points lie to the right of the directed line from ppp to qqq ; then chain the found edges into a clockwise list.What is its running time for nnn points, and why?
O(n3)\boldsymbol{O(n^3)}O(n3) n2−nn^2 - nn2−n pairs, each tested against the n−2n - 2n−2 other points: O(n3)O(n^3)O(n3) . Chaining the edges takes O(n2)O(n^2)O(n2) . The geometric insight was translated into an algorithm in a brute-force manner.
[An Example: Convex Hulls] An input situation that is "special", such as a point lying exactly on the line through two other points, is called a degenerate case, or degeneracy.
Degeneracies are ignored when first designing an algorithm, but they do arise in practice: points created by mouse clicks have small integer coordinates, so three collinear points are quite likely.
[An Example: Convex Hulls] With collinear points allowed (but no two coinciding points), when is the directed edge pqundefined\overrightarrow{pq}pq an edge of CH(P)\mathcal{CH}(P)CH(P) (the convex hull of the finite point set PPP )?
If and only if every other point r∈Pr \in Pr∈P lies either strictly to the right of the directed line through ppp and qqq , or on the open segment pq‾\overline{pq}pq .
[An Example: Convex Hulls] With collinear points allowed: pqundefined\overrightarrow{pq}pq is a convex hull edge if and only if every other point lies strictly to the right of the directed line through ppp and qqq or on the open segment pq‾\overline{pq}pq .Points a,b,ca, b, ca,b,c lie on a line in this order, and all other points lie strictly to one side of it. Which of the pairs among a,b,ca, b, ca,b,c give hull edges, and is bbb a vertex of the output?
Only the pair a,ca, ca,c (in one direction); bbb is not a vertex. bbb lies on the open segment ac‾\overline{ac}ac . For the pair a,ba, ba,b , the point ccc lies on their line but outside the open segment ab‾\overline{ab}ab , so the test fails; likewise for b,cb, cb,c .
[An Example: Convex Hulls] SlowConvexHull accepts pqundefined\overrightarrow{pq}pq as a hull edge when no point lies to the left of it. Three points p,r,qp, r, qp,r,q are nearly collinear on the left side of the point set, all other points far to their right. What can floating-point rounding do?
It can accept all three edges ( pqundefined\overrightarrow{pq}pq , prundefined\overrightarrow{pr}pr , rqundefined\overrightarrow{rq}rq ), or reject all three, leaving a gap in the hull boundary. Accepting all three is geometrically impossible, but the floating-point arithmetic doesn't know that.
[An Example: Convex Hulls] Why do rounding errors that accept or reject the wrong hull edges make SlowConvexHull crash, rather than just output a slightly wrong hull?
The edge-chaining step assumes exactly one edge starts and one edge ends at each hull vertex. With zero or two edges at a vertex, that step gets inconsistent data it was not designed to handle.
[An Example: Convex Hulls] When is a geometric algorithm called not robust?
When small errors in the computations can make it fail in completely unexpected ways. Typical cause: the correctness was proven assuming exact computation with real numbers. SlowConvexHull is correct and handles degeneracies, yet is not robust.
[An Example: Convex Hulls] What is an incremental algorithm, and how does the O(nlog⁡n)O(n \log n)O(nlogn) convex hull algorithm (ConvexHull) use the idea?
It adds the input objects one by one, updating the solution after each. ConvexHull adds the points sorted by xxx -coordinate, left to right.
[An Example: Convex Hulls] For a finite point set PPP with leftmost point p1p_1p1 and rightmost point pnp_npn , what are the upper hull and the lower hull?
Upper hull: the part of CH(P)\mathcal{CH}(P)CH(P) from p1p_1p1 clockwise to pnp_npn . Lower hull: the rest, from pnp_npn to p1p_1p1 . The upper hull contains the hull edges bounding CH(P)\mathcal{CH}(P)CH(P) from above.
[An Example: Convex Hulls] Why does the incremental convex hull algorithm (adding points sorted by xxx -coordinate) compute the upper hull and the lower hull separately?
The clockwise list of hull vertices is not sorted from left to right; on the upper hull it is. So the upper hull is built in a left-to-right scan, and the lower hull in a second, right-to-left scan.
[An Example: Convex Hulls] When you walk around the boundary of a convex polygon in clockwise order, what kind of turn do you make at every vertex?
A right turn. An arbitrary polygon has both right and left turns. This fact drives the update step of the incremental convex hull algorithm.
[An Example: Convex Hulls] ConvexHull sorts the points p1,…,pnp_1, \dots, p_np1,…,pn by xxx -coordinate and keeps the upper hull of p1,…,pi−1p_1, \dots, p_{i-1}p1,…,pi−1 in a list Lupper\mathcal{L}_{\text{upper}}Lupper , from left to right.How is Lupper\mathcal{L}_{\text{upper}}Lupper updated when pip_ipi is added?
Append pip_ipi ; then, while Lupper\mathcal{L}_{\text{upper}}Lupper has more than two points and its last three points don't make a right turn, delete the middle one of those three. The while loop stops as soon as the last three points make a right turn, or only two points are left.
[An Example: Convex Hulls] In the incremental convex hull algorithm, points are added sorted by xxx -coordinate. Why does the new point pip_ipi certainly belong to the upper hull of p1,…,pip_1, \dots, p_ip1,…,pi ?
pip_ipi is the rightmost of the points added so far, so it is an endpoint of the upper hull.
[An Example: Convex Hulls] Give the steps of the O(nlog⁡n)O(n \log n)O(nlogn) algorithm ConvexHull (P)(P)(P) .
Sort by xxx ; build Lupper\mathcal{L}_{\text{upper}}Lupper from p1,p2p_1, p_2p1,p2 , adding p3,…,pnp_3, \dots, p_np3,…,pn ; build Llower\mathcal{L}_{\text{lower}}Llower from pn,pn−1p_n, p_{n-1}pn,pn−1 , adding pn−2,…,p1p_{n-2}, \dots, p_1pn−2,…,p1 ; join the two lists. Each addition appends the point and then deletes the middle of the last three points while they don't make a right turn. Before joining, the first and last points of Llower\mathcal{L}_{\text{lower}}Llower are removed.
[An Example: Convex Hulls] ConvexHull builds the upper hull Lupper\mathcal{L}_{\text{upper}}Lupper from p1p_1p1 to pnp_npn and the lower hull Llower\mathcal{L}_{\text{lower}}Llower from pnp_npn back to p1p_1p1 , then appends Llower\mathcal{L}_{\text{lower}}Llower to Lupper\mathcal{L}_{\text{upper}}Lupper .Why are the first and last points of Llower\mathcal{L}_{\text{lower}}Llower removed before appending?
They are pnp_npn and p1p_1p1 , the points where upper and lower hull meet, which are already in Lupper\mathcal{L}_{\text{upper}}Lupper .
[An Example: Convex Hulls] The incremental convex hull algorithm sorts the points by xxx -coordinate. How does it handle points with equal xxx -coordinates?
It sorts in lexicographic order instead: by xxx -coordinate, and by yyy -coordinate when the xxx -coordinates are equal. The upper hull (solid) now runs from the lexicographically smallest to the lexicographically largest vertex; the lower hull is dotted.
[An Example: Convex Hulls] In ConvexHull's test "do the last three points make a right turn?", how must three collinear points be treated, and why?
As a left turn: the test returns true only for a strict right turn. The middle point of three collinear points should not be a hull vertex, so it gets deleted. This is simpler than SlowConvexHull's degenerate test.
[An Example: Convex Hulls] What can floating-point rounding errors do to the output of ConvexHull (the incremental, right-turn based algorithm), and what is still guaranteed?
Hull points may be dropped or inner points kept, but the output is always a closed polygonal chain of (almost) right turns. Also, no input point can lie far outside the computed hull.Remaining problem: for three points very close together, a sharp left turn can be taken for a right turn, giving a dent. Remedy: treat points that are very close as the same point, e.g. by rounding.
[An Example: Convex Hulls] Theorem 1.1 The convex hull of a set of nnn points in the plane can be computed in … ?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) time. By the incremental algorithm ConvexHull: lexicographic sort, then an upper hull and a lower hull scan.
[An Example: Convex Hulls] ConvexHull adds the lexicographically sorted points p1,…,pnp_1, \dots, p_np1,…,pn to the upper hull list Lupper\mathcal{L}_{\text{upper}}Lupper one by one; after appending pip_ipi , it deletes middle points of the last three until they make a right turn.The correctness proof is by induction on iii . After adding pip_ipi , Lupper\mathcal{L}_{\text{upper}}Lupper is a chain of right turns from p1p_1p1 to pip_ipi . What remains to show, and why is it true?
That no point lies above the new chain. Such a point would have to lie in the vertical slab between pi−1p_{i-1}pi−1 and pip_ipi , which is empty. By induction no point lay above the old chain, and the new chain lies above the old one outside that slab. A point inside the slab would come between pi−1p_{i-1}pi−1 and pip_ipi in the lexicographic order.
[An Example: Convex Hulls] ConvexHull's upper hull scan: for i=3,…,ni = 3, \dots, ni=3,…,n , append pip_ipi to Lupper\mathcal{L}_{\text{upper}}Lupper , then while the last three points don't make a right turn, delete the middle one.Why does the whole scan take only O(n)O(n)O(n) time, although a single while loop can run many times?
Each extra while-loop execution deletes a point, and each point is deleted at most once: at most nnn extra executions in total. The for loop runs n−2n - 2n−2 times, each with at least one while test. With the O(nlog⁡n)O(n \log n)O(nlogn) sort, the total is O(nlog⁡n)O(n \log n)O(nlogn) .
[An Example: Convex Hulls] Which two primitive operations does the O(nlog⁡n)O(n \log n)O(nlogn) convex hull algorithm ConvexHull need?
Lexicographic sorting, and a test whether three consecutive points make a right turn.
[Degeneracies and Robustness] Which three phases does the development of a geometric algorithm often go through?
1. Design for the general case, ignoring degeneracies. 2. Make the algorithm correct for degeneracies. 3. Implement it. Implementation means dealing with primitive operations and with inexact arithmetic.
[Degeneracies and Robustness] When adjusting an algorithm to handle degenerate cases, what do beginners tend to do, and what is often the better way?
Beginners add a huge number of case distinctions; better is to reconsider the geometry and integrate the special cases with the general case. e.g. in the convex hull algorithm, the lexicographic order instead of the order on xxx -coordinate handles points with equal xxx -coordinate.
[Degeneracies and Robustness] What is a general position assumption? Give the example from the convex hull problem.
An assumption that the input contains no degenerate cases, e.g. no three points are collinear and no two points have the same xxx -coordinate.
[Degeneracies and Robustness] Why are general position assumptions usually justified in theory, and what is the problem with them in practice?
Theory: degeneracies can almost always be handled without raising the asymptotic complexity. Practice: real inputs violate the assumptions. And special cases definitely increase the complexity of implementations.So an integrated treatment of special cases is normally the best way.
[Degeneracies and Robustness] General techniques that let you ignore special cases during design and implementation and still get an algorithm that is correct in the presence of degeneracies are called symbolic perturbation schemes.
[Degeneracies and Robustness] In the implementation phase, the assumption of exact arithmetic with real numbers breaks down. Which three ways of dealing with robustness does the book list?
Exact arithmetic; adapting the algorithm to detect inconsistencies and not crash; predicting the needed precision from the input. Exact arithmetic (integers, rationals or algebraic numbers) is slow.With option 2 the output isn't guaranteed correct, so one must establish exactly which properties it has, as for the convex hull algorithm: its output is close to the hull and structurally correct, but possibly not convex.
[Degeneracies and Robustness] When is exact arithmetic the preferred way to deal with robustness, and when is careful floating-point arithmetic good enough?
Exact: when speed is no issue. Floating point: when slight imprecision is unnoticeable, e.g. when displaying a convex hull.
[Application Domains] From which four application areas do most of the book's motivating examples come?
Computer graphics, robotics, geographic information systems (GIS), and CAD/CAM.
[Application Domains] Name typical geometric questions in 2-dimensional computer graphics.
Intersections of primitives, which primitive the mouse points to, and which primitives lie within a given region.
[Application Domains] What is hidden surface removal in 3-dimensional computer graphics?
Determining the part of a scene that is visible from a particular viewpoint, i.e. discarding the parts that lie behind other objects. Other geometric problems in 3D graphics: shadows (ray tracing, radiosity), and collision detection for moving objects and virtual reality.
[Application Domains] Robotics: how is motion planning related to task planning?
Motion planning is one aspect of task planning: for a high-level task such as "vacuum the room", the robot must also plan the order of subtasks, and so on.
[Application Domains] Which geometric problem treated in the book can be used for optimal placement of robot arms?
The smallest enclosing disc problem. Other robotics problems: parts must be supplied so that a robot arm can grasp them easily, immobilized, or turned to a known orientation.
[Application Domains] Give geometric problems that arise in geographic information systems (GIS).
Storing maps for fast location and display, interpolating heights, map overlay, and nearest facilities (Voronoi diagrams). e.g. a car guidance system must locate the car and select a small portion of a huge road map for display.The amount of data is huge, so efficient algorithms are a must.
[Application Domains] In a GIS, the height of a terrain is known only at certain sample points. Which geometric questions does this raise?
How to obtain the height elsewhere by interpolating between nearby sample points, and which sample points to choose.
[Application Domains] Give examples of GIS queries that need the overlay of different maps.
Which houses lie in a forest; where bridges are (roads crossing rivers); a slightly hilly, cheap area near a town for a golf course. A GIS usually stores different types of data in separate maps.
[Application Domains] Which geometric problems do CAD packages have to deal with?
Intersections and unions of objects, decomposing objects and their boundaries into simpler shapes, and visualizing the designed products. Simulations replace prototypes for testing, e.g. the heat emission of a printed circuit board. CAM (manufacturing) raises further geometric problems.
[Application Domains] What is design for assembly in CAD/CAM?
Taking assembly decisions into account already during the design stage. e.g. can the product be built easily with a certain manufacturing process? Many such questions need geometric algorithms.
[Application Domains] Give geometric problems from molecular modeling and from pattern recognition.
Molecules: the surface of a union of atom balls, and where two molecules can touch. Pattern recognition: how well two shapes resemble each other. The second arises in optical character recognition, matching a scanned character against stored ones.
[Application Domains] How can computational geometry help with queries on records in a database?
Interpret the records as points in a higher-dimensional space and use a geometric data structure to answer the queries efficiently.
[Notes and Comments] The O(nlog⁡n)O(n \log n)O(nlogn) convex hull algorithm that sorts the points and builds the upper and lower hulls with right-turn tests is commonly known as Graham's scan.
It is based on Andrew's modification of one of the earliest algorithms, by Graham.
[Notes and Comments] What is the lower bound for computing the convex hull of nnn points in the plane, and why do output-sensitive algorithms still make sense?
Ω(nlog⁡n)\boldsymbol{\Omega(n \log n)}Ω(nlogn) ; but in many applications only few points are on the hull, while the lower bound assumes (almost) all are. Output-sensitive bounds depend on hhh , the complexity (number of vertices) of the convex hull.
[Notes and Comments] hhh is the number of vertices of the convex hull of nnn points. What is the running time of Jarvis's march, and what is the best output-sensitive bound?
Jarvis's march (wrapping): O(h⋅n)O(h \cdot n)O(h⋅n) . Best: O(nlog⁡h)O(n \log h)O(nlogh) , by Kirkpatrick and Seidel; Chan later found a much simpler algorithm with the same bound.
[Notes and Comments] How fast can a planar convex hull be maintained dynamically?
Insertions only: O(log⁡n)O(\log n)O(logn) per insertion. Insertions and deletions: O(log⁡2n)O(\log^2 n)O(log2n) per update (Overmars and van Leeuwen).
[Notes and Comments] How fast can convex hulls be computed in dimension 3, and what changes in higher dimensions?
In 3 dimensions, still O(nlog⁡n)O(n \log n)O(nlogn) time. Above 3, the complexity of the convex hull is no longer linear in the number of points.
[Notes and Comments] What do symbolic perturbation schemes do, and what are their drawbacks?
They perturb the input symbolically so that degeneracies disappear. Drawbacks: slower algorithms, and recovering the real result can be hard. So Burnikel et al. claimed that dealing directly with degenerate inputs is simpler and more efficient.
[Notes and Comments] Most geometric comparisons can be formulated as the sign of a determinant. What goes wrong with declaring the determinant zero whenever its floating-point value is below a small threshold ε\varepsilonε ?
It can produce inconsistencies that make the program fail, e.g. deciding a=ba = ba=b and b=cb = cb=c but a≠ca \ne ca=c for three points a,b,ca, b, ca,b,c . Alternative: exact arithmetic, computing as many bits of the determinant as are needed to determine its sign.