Ch.14: Quadtrees
From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 14.1. Uniform and Non-Uniform Meshes 14.2. Quadtrees for Point Sets 14.3. From Quadtrees to Meshes 14.4. Notes and Comments
55 flashcards · Mathematics · by lakesare
Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses
[Quadtrees] Chapter opener: why does one want a mesh of a printed circuit board?
To simulate the heat emission of the board with finite element methods. The board is divided into small elements (usually triangles or quadrilaterals); the heat each element emits and how neighboring elements influence each other give a big system of equations that is solved numerically. Triangular mesh of part of a printed circuit board.
[Quadtrees] In a finite element method, why not simply use a very fine mesh everywhere?
The computation time increases drastically with the number of elements, so the mesh should be fine only where necessary. Finer meshes give better solutions; fineness is usually needed at the borders between regions of different material. Elements should also respect those borders, and very thin triangles slow down the convergence of the numerical process.
[Uniform and Non-Uniform Meshes] What is the input of the chapter's mesh generation problem?
The square [0:U]×[0:U][0:U] \times [0:U][0:U]×[0:U] , U=2jU = 2^jU=2j , with disjoint polygonal components inside, whose vertices have integer coordinates and whose edges have only the orientations 0°,45°,90°,135°0°, 45°, 90°, 135°0°,45°,90°,135° . The components of a circuit board inside the square.
[Uniform and Non-Uniform Meshes] The square together with the components inside it is called the domain of the mesh.
[Uniform and Non-Uniform Meshes] What is a triangular mesh of a square?
A subdivision of the square into triangles.
[Uniform and Non-Uniform Meshes] When is a triangular mesh conforming?
No triangle has a vertex of another triangle in the interior of one of its edges.
[Uniform and Non-Uniform Meshes] When does a triangular mesh respect the input?
The edges of the components are contained in the union of the edges of the mesh triangles.
[Uniform and Non-Uniform Meshes] When are the triangles of the chapter's mesh well-shaped?
All their angles lie between 45°45°45° and 90°90°90° . In general: angles neither too large nor too small.
[Uniform and Non-Uniform Meshes] When is a mesh non-uniform (in the chapter's sense)?
It is fine near the edges of the components and coarse far away from them.
[Uniform and Non-Uniform Meshes] Which four properties must the chapter's triangular mesh of a domain have? (The picture shows violations.)
Conforming, respects the input, well-shaped, non-uniform. Conforming: no vertex inside another triangle's edge. Respects the input: component edges are mesh edges. Well-shaped: angles in [45°,90°][45°, 90°][45°,90°] . Non-uniform: fine only near component edges.
[Uniform and Non-Uniform Meshes] The Delaunay triangulation maximizes the minimum angle. Why is the Delaunay triangulation of the component vertices still no solution to the mesh problem?
It need not respect the component edges, and it can still have angles that are too small. Example: a square of side 16 with one unit-square component at distance 1 from the left and top sides gives Delaunay triangles with an angle below 5°5°5° .
[Uniform and Non-Uniform Meshes] What are Steiner points?
Extra points, not in the input, used as vertices of the mesh to obtain well-shaped triangles. A triangulation that uses Steiner points is a Steiner triangulation. The Delaunay triangulation only maximizes the minimum angle over triangulations of the given points, so Steiner points can beat it.
[Uniform and Non-Uniform Meshes] A square of side 16 contains one unit-square component. How does a uniform mesh with only well-shaped triangles look, and what is its drawback?
A Steiner point at every grid point, each grid cell cut by a diagonal (triangles 45°,45°,90°45°, 45°, 90°45°,45°,90° ); drawback: small triangles everywhere, so many triangles. Uniform mesh: 512 triangles. Non-uniform mesh, triangles growing away from the component: 52.
[Uniform and Non-Uniform Meshes] A square of side 16 is meshed uniformly: every unit grid cell is cut into two 45°45°45° - 45°45°45° - 90°90°90° triangles. The only component is a unit square near the top left corner.Why can't you just replace all triangles of the bottom right quarter by two big triangles?
The mesh would no longer be conforming: the small triangles next to the quarter would have vertices in the interior of the big triangles' edges. Instead the triangle size must grow gradually away from the component.
[Quadtrees for Point Sets] What is a quadtree?
A rooted tree in which every internal node has four children, and the children's squares are the four quadrants of the parent's square. The children are labelled NE, NW, SW, SE by quadrant. A quadtree and its subdivision.
[Quadtrees for Point Sets] What is the quadtree subdivision of a quadtree?
The subdivision of the root's square formed by the squares of the leaves.
[Quadtrees for Point Sets] For a square face of a quadtree subdivision: what are its corners, sides and edges?
Corners: its four corner vertices. Sides: segments between consecutive corners. Edges: subdivision edges on its boundary. A side contains at least one, possibly many, edges; a face can have more than four vertices but is still called a square.
[Quadtrees for Point Sets] Two squares of a quadtree subdivision are neighbors if they share an edge.
[Quadtrees for Point Sets] How is the quadtree for a point set PPP inside a square σ=[xσ:xσ′]×[yσ:yσ′]\sigma = [x_\sigma : x'_\sigma] \times [y_\sigma : y'_\sigma]σ=[xσ:xσ′]×[yσ:yσ′] defined?
If ∣P∣≤1|P| \le 1∣P∣≤1 : a single leaf storing PPP and σ\sigmaσ . Otherwise: a root storing σ\sigmaσ , whose four children are quadtrees for the points of PPP in each quadrant of σ\sigmaσ . The quadrants are split at xmid=(xσ+xσ′)/2x_{\mathrm{mid}} = (x_\sigma + x'_\sigma)/2xmid=(xσ+xσ′)/2 and ymid=(yσ+yσ′)/2y_{\mathrm{mid}} = (y_\sigma + y'_\sigma)/2ymid=(yσ+yσ′)/2 . The square of node vvv is written σ(v)\sigma(v)σ(v) .
[Quadtrees for Point Sets] A quadtree for points splits a square at xmidx_{\mathrm{mid}}xmid and ymidy_{\mathrm{mid}}ymid , with PNE={p:px>xmid, py>ymid}P_{\mathrm{NE}} = \{p : p_x > x_{\mathrm{mid}},\ p_y > y_{\mathrm{mid}}\}PNE={p:px>xmid, py>ymid} and the other three sets defined with ≤\le≤ and >>> accordingly. Which quadrants get the points on the splitting lines?
The vertical line belongs to the two left (west) quadrants, the horizontal line to the two lower (south) quadrants. So the center point goes to SW. PNWP_{\mathrm{NW}}PNW : px≤xmidp_x \le x_{\mathrm{mid}}px≤xmid , py>ymidp_y > y_{\mathrm{mid}}py>ymid ; PSWP_{\mathrm{SW}}PSW : both ≤\le≤ ; PSEP_{\mathrm{SE}}PSE : px>xmidp_x > x_{\mathrm{mid}}px>xmid , py≤ymidp_y \le y_{\mathrm{mid}}py≤ymid .
[Quadtrees for Point Sets] Must every quadtree node vvv store its square σ(v)\sigma(v)σ(v) ?
No: storing only the root's square suffices, and the square of the current node is maintained while walking down. This saves storage at the cost of extra computation during queries.
[Quadtrees for Point Sets] How is a quadtree for a point set PPP constructed, and with which square does it start?
Recursively: split the square into quadrants, partition the points, recurse on each quadrant; stop when fewer than two points remain. The start square is given as input, or a smallest enclosing square of PPP is computed in linear time from the extreme points in the xxx - and yyy -directions.
[Quadtrees for Point Sets] Why can't the size and depth of a quadtree be bounded in terms of the number nnn of points alone?
Splitting the square need not split the point set: all points can lie in the same quadrant, again and again. So a quadtree can be very unbalanced; its depth depends on how close the points are compared to the square's size.
[Quadtrees for Point Sets] Lemma 14.1 PPP is a set of points in the plane, ccc the smallest distance between two points of PPP , and sss the side length of the initial square. The depth of the quadtree for PPP is at most … ?
log(s/c)+32\boldsymbol{\log(s/c) + \tfrac{3}{2}}log(s/c)+23 log\loglog is base 2.
[Quadtrees for Point Sets] The depth of a quadtree for a point set PPP is at most log(s/c)+32\log(s/c) + \frac{3}{2}log(s/c)+23 , where ccc is the smallest distance between two points of PPP and sss is the side length of the initial square.What is the key idea of the proof?
A node at depth iii has a square of side s/2is/2^is/2i , whose diagonal s2/2is\sqrt{2}/2^is2/2i must be at least ccc if the node is internal (it contains two points). So an internal node has i≤log(s2/c)=log(s/c)+12i \le \log(s\sqrt{2}/c) = \log(s/c) + \frac{1}{2}i≤log(s2/c)=log(s/c)+21 , and the tree's depth is one more than the deepest internal node. Depth 3: side length s/8s/8s/8 .
[Quadtrees for Point Sets] Theorem 14.2 A quadtree of depth ddd storing a set of nnn points has how many nodes, and how fast can it be constructed?
O((d+1)n)\boldsymbol{O((d+1)n)}O((d+1)n) nodes, construction in O((d+1)n)\boldsymbol{O((d+1)n)}O((d+1)n) time.
[Quadtrees for Point Sets] A quadtree of depth ddd storing nnn points has O((d+1)n)O((d+1)n)O((d+1)n) nodes.How does the proof bound the number of nodes?
At each depth there are at most nnn internal nodes, and the leaves number one plus three times the internal nodes. The squares at one depth are disjoint, and every internal node's square contains at least one point.
[Quadtrees for Point Sets] A quadtree of depth ddd storing nnn points can be built in O((d+1)n)O((d+1)n)O((d+1)n) time.Why?
The work at an internal node is linear in the number of points in its square, and the squares at one depth together contain at most nnn points. The dominating step is distributing the points over the four quadrants.
[Quadtrees for Point Sets] What does neighbor finding in a quadtree compute, for a node vvv and a direction (north, east, south or west)?
A node v′v'v′ whose square σ(v′)\sigma(v')σ(v′) is adjacent to σ(v)\sigma(v)σ(v) in that direction: one at the same depth as vvv if it exists, otherwise the deepest such node. It reports nil if σ(v)\sigma(v)σ(v) lies on that side of the initial square. Usually vvv is a leaf and one wants a leaf back.
[Quadtrees for Point Sets] NorthNeighbor (v,T)(v, \mathcal{T})(v,T) , for a node vvv of a quadtree T\mathcal{T}T , returns the deepest node v′v'v′ with depth at most that of vvv whose square σ(v′)\sigma(v')σ(v′) is adjacent to σ(v)\sigma(v)σ(v) on its north side, or nil if there is none.How does NorthNeighbor (v,T)(v, \mathcal{T})(v,T) work when vvv is the root, or the SW- or SE-child of its parent?
Root: nil. SW-child: return the NW-child of the parent. SE-child: return the NE-child of the parent.
[Quadtrees for Point Sets] NorthNeighbor (v,T)(v, \mathcal{T})(v,T) , for a node vvv of a quadtree T\mathcal{T}T , returns the deepest node v′v'v′ with depth at most that of vvv whose square σ(v′)\sigma(v')σ(v′) is adjacent to σ(v)\sigma(v)σ(v) on its north side, or nil if there is none.How does NorthNeighbor (v,T)(v, \mathcal{T})(v,T) work when vvv is the NW- or NE-child of its parent?
μ\muμ := NorthNeighbor(parent( vvv )); if μ\muμ is nil or a leaf, return μ\muμ , else return μ\muμ 's SW-child ( vvv a NW-child) or SE-child ( vvv a NE-child). Here vvv is a NW-child; its north-neighbor is the SW-child of the parent's north-neighbor.
[Quadtrees for Point Sets] NorthNeighbor (v,T)(v, \mathcal{T})(v,T) , for a node vvv of a quadtree T\mathcal{T}T , returns the deepest node v′v'v′ with depth at most that of vvv whose square σ(v′)\sigma(v')σ(v′) is adjacent to σ(v)\sigma(v)σ(v) on its north side, or nil if there is none.NorthNeighbor may return an internal node. How do you get the leaf whose square is adjacent to σ(v)\sigma(v)σ(v) ?
Walk down the quadtree from the reported node, always going to a south-child.
[Quadtrees for Point Sets] Theorem 14.3 T\mathcal{T}T is a quadtree of depth ddd . How fast can the neighbor of a node in a given direction be found (the same-depth node with adjacent square, or the deepest such node)?
O(d+1)\boldsymbol{O(d+1)}O(d+1) time. Each recursive call takes O(1)O(1)O(1) time and moves to the parent, so the depth of the argument drops by one per call.
[Quadtrees for Point Sets] When is a quadtree subdivision balanced, and what does that mean for the leaves of the quadtree?
Any two neighboring squares differ by at most a factor two in size; so leaves with neighboring squares differ by at most one in depth. Not balanced: large squares adjacent to many small ones, which is unwanted for meshing.
[Quadtrees for Point Sets] A quadtree subdivision is balanced if any two neighboring squares (squares sharing an edge) differ by at most a factor two in size.How does BalanceQuadTree( T\mathcal{T}T ) make a quadtree balanced?
Work through a list of leaves: split each leaf whose square must be split, and add its four children and its neighbors that now need splitting to the list. The list L\mathcal{L}L starts with all leaves; the loop runs until L\mathcal{L}L is empty. If a split leaf stores a point, the point moves to the correct new leaf. Original subdivision solid, the refinement from balancing dotted.
[Quadtrees for Point Sets] A quadtree subdivision is balanced if any two neighboring squares (squares sharing an edge) differ by at most a factor two in size.NorthNeighbor (v,T)(v, \mathcal{T})(v,T) , for a node vvv of a quadtree T\mathcal{T}T , returns the deepest node v′v'v′ with depth at most that of vvv whose square σ(v′)\sigma(v')σ(v′) is adjacent to σ(v)\sigma(v)σ(v) on its north side, or nil if there is none.While balancing, how do you test whether a leaf square σ(μ)\sigma(\mu)…
σ(μ)\sigma(\mu)σ(μ) must be split iff NorthNeighbor (μ,T)(\mu, \mathcal{T})(μ,T) reports a node with a SW- or SE-child that is not a leaf. That means a north neighbor less than half the size of σ(μ)\sigma(\mu)σ(μ) .
[Quadtrees for Point Sets] A quadtree subdivision is balanced if any two neighboring squares (squares sharing an edge) differ by at most a factor two in size.NorthNeighbor (v,T)(v, \mathcal{T})(v,T) , for a node vvv of a quadtree T\mathcal{T}T , returns the deepest node v′v'v′ with depth at most that of vvv whose square σ(v′)\sigma(v')σ(v′) is adjacent to σ(v)\sigma(v)σ(v) on its north side, or nil if there is none.After splitting σ(μ)\sigma(\mu)σ(μ) while balancing, how do you test w…
It does iff NorthNeighbor (μ,T)(\mu, \mathcal{T})(μ,T) reports a node whose square is larger than σ(μ)\sigma(\mu)σ(μ) . That neighbor is now adjacent to the quadrants of σ(μ)\sigma(\mu)σ(μ) , which are less than half its size.
[Quadtrees for Point Sets] Theorem 14.4 T\mathcal{T}T is a quadtree with mmm nodes and depth ddd . How many nodes has the balanced version of T\mathcal{T}T , and how fast can it be constructed?
O(m)\boldsymbol{O(m)}O(m) nodes, constructed in O((d+1)m)\boldsymbol{O((d+1)m)}O((d+1)m) time. Even though large squares next to tiny ones get split many times and splits can propagate.
[Quadtrees for Point Sets] Balancing a quadtree T\mathcal{T}T with mmm nodes performs splits (a leaf becomes an internal node with four leaves). Old squares: squares of nodes of T\mathcal{T}T ; new squares: those created by balancing.How does the proof show that the balanced tree has O(m)O(m)O(m) nodes?
Charge each split of σ\sigmaσ to an old square among the 8 equal-sized squares around σ\sigmaσ ; so at most 8m8m8m splits. Each old square is charged at most 8 times, and each split adds 4 nodes.
[Quadtrees for Point Sets] Balancing a quadtree performs splits. Old squares: squares of nodes of the original quadtree; new squares: those created by balancing. A square is split when it is adjacent to a square of less than half its size.Why is at least one of the eight equal-sized squares surrounding a split square old?
A smallest counterexample σ\sigmaσ gives a smaller one: the half-size square σ′\sigma'σ′ next to σ\sigmaσ that contains the small neighbor. σ′\sigma'σ′ lies in one of the eight (new) squares around σ\sigmaσ , so σ′\sigma'σ′ is new, hence was split. Its eight surrounding squares lie in those new squares or in σ\sigmaσ , whose quadrants are new since σ\sigmaσ is split by balancing. So none is old.
[Quadtrees for Point Sets] Balancing a quadtree T\mathcal{T}T with mmm nodes and depth ddd produces O(m)O(m)O(m) nodes.Why does BalanceQuadTree take O((d+1)m)O((d+1)m)O((d+1)m) time?
Each node is handled at most once, with a constant number of neighbor-finding operations of O(d+1)O(d+1)O(d+1) time each.
[From Quadtrees to Meshes] Mesh input: the square [0:U]×[0:U][0:U] \times [0:U][0:U]×[0:U] with U=2jU = 2^jU=2j , containing disjoint polygonal components whose vertices have integer coordinates and whose edges make an angle of 0°0°0° , 45°45°45° , 90°90°90° or 135°135°135° with the xxx -axis.When does the quadtree construction for mesh generation stop splitting a square?
When the square has unit size, or its closure is no longer intersected by any component edge. Squares and edges are closed, so an edge lying in a side of a square intersects that square. Result: component edges are surrounded by unit squares, and squares grow farther away (non-uniform).
[From Quadtrees to Meshes] Mesh input: the square [0:U]×[0:U][0:U] \times [0:U][0:U]×[0:U] with U=2jU = 2^jU=2j , containing disjoint polygonal components whose vertices have integer coordinates and whose edges make an angle of 0°0°0° , 45°45°45° , 90°90°90° or 135°135°135° with the xxx -axis.Squares are split while larger than unit size and their closure meets a component edge.How can a component edge intersect the interior of a square of the final subdivision, and why?
Only as a diagonal of the square. Intersected squares have unit size and component vertices are integer points, so horizontal and vertical edges cannot cross a square's interior, and 45°45°45° or 135°135°135° edges must run along a diagonal.
[From Quadtrees to Meshes] Goal: a triangular mesh of the square that is conforming (no triangle has a vertex of another triangle in the interior of one of its edges), respects the input (component edges lie in the union of mesh edges), is well-shaped (all angles between 45°45°45° and 90°90°90° ) and is non-uniform (fine near component edges, coarse far from them).Why not triangulate the (unbalanced) mesh quadtree subdivision by adding a diagonal to every square not crossed by a component edge?
The mesh would not be conforming: vertices of smaller neighbors lie inside the squares' sides. Triangulating with those side vertices included fixes that, but a square with many vertices on a side then gets badly shaped triangles.
[From Quadtrees to Meshes] In a balanced quadtree subdivision, neighboring squares differ by at most a factor two in size.How is each square of a balanced subdivision triangulated into well-shaped triangles?
No vertex inside a side: add a diagonal. Otherwise: add a Steiner point at the center and connect it to all boundary vertices. By balance each side has at most one interior vertex, at its midpoint, so all triangles have angles 45°,45°,90°45°, 45°, 90°45°,45°,90° . Squares already cut by a component diagonal keep that diagonal.
[From Quadtrees to Meshes] Mesh input: the square [0:U]×[0:U][0:U] \times [0:U][0:U]×[0:U] with U=2jU = 2^jU=2j , containing disjoint polygonal components whose vertices have integer coordinates and whose edges make an angle of 0°0°0° , 45°45°45° , 90°90°90° or 135°135°135° with the xxx -axis.What are the steps of GenerateMesh?
Build a quadtree, balance it, build the DCEL of its subdivision, triangulate each square. Quadtree: split a square while it is larger than unit size and its closure meets a component. Per square: crossed by a component edge: add that diagonal; only corner vertices: add a diagonal; otherwise: Steiner point in the center joined to all boundary vertices. The mesh is output as a doubly-connected edge list.
[From Quadtrees to Meshes] Theorem 14.5 Mesh input: the square [0:U]×[0:U][0:U] \times [0:U][0:U]×[0:U] with U=2jU = 2^jU=2j , containing disjoint polygonal components whose vertices have integer coordinates and whose edges make an angle of 0°0°0° , 45°45°45° , 90°90°90° or 135°135°135° with the xxx -axis. SSS is the set of components and p(S)p(S)p(S) the sum of their perimeters. A conforming, non-uniform mesh respecting the input with only well-shaped triangles exists. How many triangles does…
O(p(S)logU)\boldsymbol{O(p(S) \log U)}O(p(S)logU) triangles, built in O(p(S)log2U)\boldsymbol{O(p(S) \log^2 U)}O(p(S)log2U) time.
[From Quadtrees to Meshes] The mesh quadtree splits a square while it is larger than unit size and its closure meets an edge of a component of SSS ; p(S)p(S)p(S) is the sum of the perimeters of the components, inside the square [0:U]×[0:U][0:U] \times [0:U][0:U]×[0:U] .Why does this quadtree have O(p(S)logU)O(p(S) \log U)O(p(S)logU) nodes?
A segment of length lll meets the closure of at most 4+3l/24 + 3l/\sqrt{2}4+3l/2 grid cells, so each depth has O(p(S))O(p(S))O(p(S)) internal nodes; the depth is O(logU)O(\log U)O(logU) . The cell bound holds for unit cells and so also for larger cells. The depth is O(logU)O(\log U)O(logU) because splitting stops at unit size.
[From Quadtrees to Meshes] The quadtree built for the mesh (before balancing) has O(p(S)logU)O(p(S) \log U)O(p(S)logU) nodes, where p(S)p(S)p(S) is the total perimeter of the components.Why is the final number of mesh triangles also O(p(S)logU)O(p(S) \log U)O(p(S)logU) ?
Balancing keeps the number of nodes linear, and each square is cut into a constant number of triangles.
[From Quadtrees to Meshes] Mesh generation: build a quadtree (split while larger than unit size and the closure meets a component edge), balance it, then triangulate. The quadtree has O(p(S)logU)O(p(S) \log U)O(p(S)logU) nodes and depth O(logU)O(\log U)O(logU) ; p(S)p(S)p(S) is the total perimeter of the components.Where does the construction time O(p(S)log2U)O(p(S) \log^2 U)O(p(S)log2U) come from?
Building the quadtree takes O(p(S)logU)O(p(S) \log U)O(p(S)logU) ; balancing mmm nodes of a depth- ddd tree takes O((d+1)m)O((d+1)m)O((d+1)m) , an extra factor O(logU)O(\log U)O(logU) . Splitting a node costs time linear in the component edges meeting its closure, which sums to O(p(S))O(p(S))O(p(S)) per depth. The DCEL and the triangulation fit within the same time.
[Notes and Comments] Who developed quadtrees, and when?
Finkel and Bentley, 1974. One of the first data structures for higher-dimensional data.
[Notes and Comments] What is a compressed quadtree, and what is its advantage?
A quadtree with the nodes that have only one non-empty subtree removed; it has linear size. An ordinary quadtree's size can't be bounded in the number nnn of points. Combined with skip lists (Eppstein et al.), it supports insertions, deletions and searches in O(logn)O(\log n)O(logn) time.
[Notes and Comments] The generalization of quadtrees to higher dimensions is usually called octrees.
[Notes and Comments] The aspect ratio of a triangle is its longest side divided by the height onto that side; a triangle with smallest angle θ\thetaθ has aspect ratio between 1/sinθ1/\sin\theta1/sinθ and 2/sinθ2/\sin\theta2/sinθ .Why does a mesh of a 1×A1 \times A1×A rectangle with all angles at least 30°30°30° need Ω(A)\Omega(A)Ω(A) triangles?
Each triangle has height at most 1 and aspect ratio at most 2/sin30°=42/\sin 30° = 42/sin30°=4 , so area O(1)O(1)O(1) , while the rectangle has area AAA . So the number of triangles depends on the domain's shape, not only on its number of vertices.
[Notes and Comments] How many non-obtuse triangles (all angles at most 90°90°90° ) are needed to mesh any polygonal domain with nnn vertices?
O(n)\boldsymbol{O(n)}O(n) (Bern et al.), improving the earlier O(n2)O(n^2)O(n2) of Bern and Eppstein.