UBC Faculty Research and Publications

Table Cartogram Evans, William; Felsner, Stefan; Kaufmann, Michael; Kobourov, Stephen G.; Mondal, Debajyoti; Nishat, Rahnuma Islam; Verbeek, Kevin Jan 3, 2016

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
52383-Evans_W_et_al_Table_cartogram.pdf [ 412.56kB ]
Metadata
JSON: 52383-1.0349076.json
JSON-LD: 52383-1.0349076-ld.json
RDF/XML (Pretty): 52383-1.0349076-rdf.xml
RDF/JSON: 52383-1.0349076-rdf.json
Turtle: 52383-1.0349076-turtle.txt
N-Triples: 52383-1.0349076-rdf-ntriples.txt
Original Record: 52383-1.0349076-source.json
Full Text
52383-1.0349076-fulltext.txt
Citation
52383-1.0349076.ris

Full Text

Table CartogramIWilliam EvansDepartment of Computer Science, University of British ColumbiaStefan FelsnerInstitut fu¨r Mathematik, Technische Universita¨t BerlinMichael KaufmannWilhelm-Schickard-Institut fu¨r Informatik, Universita¨t Tu¨bingenStephen G. KobourovDepartment of Computer Science, University of ArizonaDebajyoti MondalDepartment of Computer Science, University of ManitobaRahnuma Islam NishatDepartment of Computer Science, University of VictoriaKevin VerbeekDepartment of Mathematics and Computer Science, TU EindhovenAbstractA table cartogram of a two dimensional m×n table A of non-negative weights ina rectangle R, whose area equals the sum of the weights, is a partition of R intoconvex quadrilateral faces corresponding to the cells of A such that each facehas the same adjacency as its corresponding cell and has area equal to the cell’sweight. Such a partition acts as a natural way to visualize table data arising invarious fields of research. In this paper, we give a O(mn)-time algorithm to finda table cartogram in a rectangle. We then generalize our algorithm to obtaintable cartograms inside arbitrary convex quadrangles, circles, and finally, on thesurface of cylinders and spheres.IA preliminary version of the paper appeared in the Proceedings of the 21st Annual Eu-ropean Symposium on Algorithms (ESA 2013) [1].Email addresses: will@cs.ubc.ca (William Evans), felsner@math.tu-berlin.de (StefanFelsner), mk@informatik.uni-tuebingen.de (Michael Kaufmann), kobourov@cs.arizona.edu(Stephen G. Kobourov), jyoti@cs.umanitoba.ca (Debajyoti Mondal), rnishat@uvic.ca(Rahnuma Islam Nishat), k.a.b.verbeek@tue.nl (Kevin Verbeek)Preprint submitted to Computational Geometry January 3, 2016Keywords: Cartogram, Data Visualization, Grid Map, Tree Map.1. IntroductionA cartogram, or value-by-area diagram, is a thematic cartographic visualiza-tion, in which the areas of countries are modified in order to represent a given setof values, such as population, gross-domestic product, or other geo-referencedstatistical data. Red-and-blue population cartograms of the United States wereoften used to illustrate the results in the 2000 and 2004 presidential elections.While geographically accurate maps seemed to show an overwhelming victoryfor George W. Bush, population cartograms effectively communicated the near50-50 split, by deflating the rural and suburban central states.The challenge in creating a good cartogram is thus to shrink or grow theregions in a map so that they faithfully reflect the set of pre-specified areavalues, while still retaining their characteristic shapes, relative positions, andadjacencies as much as possible. In this paper we introduce a new table car-togram model, where the input is a two dimensional m×n table of non-negativeweights, and the output is a rectangle with area equal to the sum of the inputweights partitioned into m×n convex quadrilateral faces each with area equal tothe corresponding input weight. Figure 1 and Figure 2 show two such examples.Such a visualization preserves both area and adjacencies. Besides, it is simple,visually attractive, and applicable to many fields that require visualization ofdata table.7 9 9 662.5 10.54.52.54.5 4.5 1633 4.54Figure 1: A 4× 4 table, its table cartogram.The solution to the problem is not obvious even for a 2× 2 table. For exam-ple, Figures 3(a) and (b) show a table A and a unit square R, respectively. Oneattempt to find the cartogram of A in R may be to first split R horizontallyaccording to the sum of each row, and then to find a good split in each sub-rectangle to realize the correct areas. But this approach does not work, becausethe first split prevents the creation of the two convex quadrilaterals with area in opposite corners that share a boundary vertex, see Figure 3(c). Figure 3(d)shows a possible cartogram.The following little argument shows that 2× 2 table cartograms exist. Theargument contains some elements that will be reused for the general case. The2LaYScHfZrTiTaNbVWMoCrReTcMnOsRuFeIrRhCoPtPdNiAuAgCuHgCdZn(a) A part of the periodic table. (b) Relative Thermal ConductivityLaYScHfZrTiTaNbVWMoCrReTcMnOsRuFeIrRhCoPtPdNiAuAgCuHgCdZn(c) Relative Molar VolumeLaYScHfZrTiTaNbVWMoCrReTcMnOsRuFeIrRhCoPtPdNiAuAgCuHgCdZnLaYScHfZrTiTaNbVWMoCrReTcMnOsRuFeIrRhCoPtPdNiAuAgCuHgCdZn(d) Relative Density(e) Relative Boiling Point (f) Relative Atomic MassLaYScHfZrTiTaNbVWMoCrReTcMnOsRuFeIrRhCoPtPdNiAuAgCuHgCdZnLaYScHfZrTiTaNbVWMoCrReTcMnOsRuFeIrRhCoPtPdNiAuAgCuHgCdZnFigure 2: (a) A part of the periodic table of chemical elements. (b)–(f) Cartograms of differentchemical properties.12 − 12 − 11(a) (b) (c) (d)12 − 12 −  12 − 12 − a bc d(e) (f)c da b`pFigure 3: (a) A 2× 2 table A. (b) R. (c) An attempt to find a cartogram. (d) A cartogramof A in R. (e) A 2× 2 table A. (f) The cartogram showing ` as a dashed line.input is a 2× 2 table with four positive reals a, b, c, d with a+ b+ c+ d = 1, asshown in Figure 3(e). Rotational symmetry of the problem allows us to assumethat a+ b ≤ 1/2. Fix the unit square R with corners (0, 0), (0, 1), (1, 1), (1, 0) asthe frame for the table cartogram.Now consider the horizontal line ` with the property that every triangleT (p) with top side equal to the top side of R and one corner p on ` has areaa + b. Since a + b ≤ 1/2, the line ` intersects R in a horizontal segment. Forp ∈ ` ∩ R, the vertical line through p partitions R \ T (p) into a left 4-gon S−and a right 4-gon S+. The areas of these two 4-gons depend continuously onthe position of point p but their sum is always c+d. If p is on the left boundary,Area (S+) = c+ d, and if p is on the right boundary, Area (S+) = 0. Hence itfollows from the intermediate value theorem that there is a position for p on `∩Rsuch that Area (S−) = c and Area (S+) = d. We can now use the intermediatevalue theorem to find a partition of T (p), i.e., we find a line by rotating a linearound p such that the left triangle has area a, and the right triangle has area3WAORMTIDWYNVCAUTCONMAZKSNESDNDMNIAMOOKTXMIINILWIPAOHKYALMSARLAFLGASCNCVAWVNYMENHVTCTMARINJDEMDTN6.725 0.989 0.673 5.304 5.687 19.378 0.626 1.3283.831 1.568 0.814 3.046 9.884 12.702 1.316 6.5482.701 0.564 1.826 12.831 6.484 11.537 3.574 1.0532.764 5.029 2.853 5.989 4.339 1.853 5.774 8.79237.254 2.059 3.751 2.916 6.346 4.625 8.001 0.8986.392 25.146 4.533 2.967 4.780 9.688 18.801 9.535WA MT ND MN WI NY VT MEOR ID SD IA NI PA NH MANV WY NE IL IN OH CT RIUT CO KS MO KY WV MD NJCA NM OK AR TN SC VA DEAZ TX LA MS AL GA FL NCAZCAUTNVORWATXLAOKMSARMOILIAMNALTNKYINMIWIGASCWVOHPANYFLVAMDCTNCNJMAMEDERIVTNHNDMTSDIDWY NEKSNMCOFigure 4: A grid map of the USA [6] and our corresponding table cartogram of the populationof the states in 2010.b. The resulting partition of R into four parts is a table cartogram for theinput table, as shown in Figure 3(f). The critical reader may object that twoof the 4-gons have a degenerate side. This can be avoided by perturbing thecartogram slightly to make a very short edge instead of a point. The resultis an ε approximate cartogram without degeneracies. Another approach is tomodify the construction rules so that degeneracies are avoided. We take thisapproach in Section 2 to show the existence of non-degenerate table cartogramsin general.1.1. Related WorkThe problem of representing additional information on top of a geographicmap dates back to the 19th century, and highly schematized rectangular car-tograms can be found in the 1934 work of Raisz [2]. Recently, van Kreveld andSpeckmann describe automated methods to produce rectangular cartograms [3].With such rectangular cartograms it is not always possible to represent all ad-jacencies and areas accurately [4, 3]. However, in many “simple” cases, such asFrance, Italy and the USA, rectangular cartograms and even table cartogramsoffer a practical and straightforward schematization, e.g., Figure 4. Grid mapsare a special case of single-level spatial treemaps: the input is a geographic mapmapped onto a grid of equal-sized rectangles, in such a way as to preserve aswell as possible the relative positions of the corresponding regions [5, 6]. As weshow, such maps can always be visualized as table cartograms.Eppstein et al. studied area-universal rectangular layouts and characterized4the class of rectangular layouts for which all area-assignments can be achievedwith combinatorially equivalent layouts [7]. If the requirement that rectanglesare used is relaxed to allow the use of rectilinear regions then de Berg et al. [8]showed that all adjacencies can be preserved and all areas can be realized with40-sided regions. In a series of papers the polygon complexity that is sufficient torealize any rectilinear cartogram was decreased from 40 sides down to 8 sides [9],which is best possible due to an earlier lower bound [10].More general cartograms without restrictions to rectangular or rectilinearshapes have also been studied. For example adjacencies can be preserved andareas represented perfectly using convex quadrilaterals if the dual of the mapis an outerplanar graph [11]. Dougenik et al. introduced a method based onforce fields where the map is divided into cells and every cell has a force relatedto its data value which affects the other cells [12]. Dorling used a cellularautomaton approach, where regions exchange cells until an equilibrium has beenachieved, i.e., each region has attained the desired number of cells [13]. Thistechnique can result in significant distortions, thereby reducing readability andrecognizability. Keim et al. defined a distance between the original map and thecartogram with a metric based on Fourier transforms, and then used a scan-linealgorithm to reposition the edges so as to optimize the metric [14]. Gastner andNewman [15] project the original map onto a distorted grid, calculated so thatcell areas match the pre-defined values. The desired areas are then achievedvia an iterative diffusion process inspired by physical intuition. The cartogramsproduced this way are mostly readable but the complexity of the polygons canincrease significantly. Edelsbrunner and Waupotitsch [16] generated cartogramsusing a sequence of homeomorphic deformations. Kocmoud and House [17]described a technique that combines the cell-based approach of Dorling [13]with the homeomorphic deformations of Edelsbrunner and Waupotitsch [16].There are thousands of papers, spanning over a century, and covering var-ious aspects of cartograms, from geography to geometry and from interactivevisualization to graph theory and topology. The above brief review is woefullyincomplete; the survey by Tobler [18] provides a more comprehensive overview.1.2. Our ResultsThe main construction is presented in Section 2. We start with a simpleconstructive algorithm that realizes any table inside a rectangle in which eachcell is represented by a convex quadrilateral with its prescribed weight. Theapproach relies on making many of the regions be triangles. We then modifythe method to remove such degeneracies. The construction can be implementedto run in O(mn) time, i.e., in time linear in the input size.In Section 3 we find table cartograms inside arbitrary triangles or convexquadrilaterals, which is best possible, because regular n-gons, n ≥ 5, do notalways support table cartograms (e.g., consider a table with some cell valuelarger than the maximum-area convex quadrangle that can be drawn inside then-gon). We also realize table cartograms inside circles, using circular-arcs, andon the surface of a sphere via a transformation from a realization on the cylinder.52. Table cartograms in rectanglesWe first construct a cartogram with degenerate 4-gons, where we allow theinput table to have non-negative numbers. Later we show that one can removethe degeneracies if the entries of the table are strictly positive.2.1. Cartogram with Degenerate 4-gonsThe input is a table A with m rows and n columns of non-negative numbersAi,j . Let S =∑i,j Ai,j and let Si be the sum of the numbers in row i, i.e.,Si =∑1≤j≤nAi,j . Assume, by scaling, that S > 4. Let R be the rectanglewith corners (0, 0), (S/2, 0), (S/2, 2), (0, 2). We construct the cartogram withinR and later generalize the construction to all rectangles with area S, as statedin the following theorem.Theorem 1. Let A be an m×n table of non-negative numbers Ai,j. Let R be arectangle with width w, height h and area equal to the sum of the numbers of A.Then there exists a cartogram of A in R such that every face in the cartogramis convex. The construction requires O(mn) arithmetic operations.In the rest of this section we prove Theorem 1. Let k be the largest indexsuch that the sum of the numbers in rows 1, 2, . . . , k − 1 is less than S/2. Wemay then choose λ ∈ (0, 1] such that ∑1≤i≤k−1 Si + λSk = S/2. We split thetable A into two tables At and Ab. Table At consists of k rows and n columns.The first k − 1 rows are taken from A, i.e., Ati,j = Ai,j for 1 ≤ i ≤ k − 1 and1 ≤ j ≤ n. The last row is a λ-fraction of row k from A, i.e., Atk,j = λ · Ak,jfor all j. Table Ab consists of m − k + 1 rows and n columns. The first rowaccommodates the remaining portion of row k from A, i.e., Ab1,j = (1−λ) ·Ak,j .All the other rows are taken from A, i.e., Abi,j = Ai+k−1,j for i > 1 and all j.An example is shown in Figure 5(a). If λ = 1, then Ab contains a top row ofzeros.Let Dtj be the sum of entries in columns 2j − 2 and 2j − 1 from At, where1 ≤ j ≤ bm/2 + 1c. Note that Dt1 is only responsible for one column. Thesame may hold for the last Dtj depending on the parity of m. Similarly, Dbl isthe sum of entries in columns 2l − 1 and 2l from Ab, where 1 ≤ l ≤ dm/2e.Again, depending on the parity of m the last Dbl may only be responsible forone column.We now define a zig-zag Z in R (formally, Z is a polygonal line) such thatthe areas of the triangles defined by Z are the numbers Dt1, Db1, Dt2, Db2, Dt3, . . . inthis order. The zig-zag starts at z0 = (0, 0). Since the height of R is 2, the firstsegment ends at z1 = (Dt1, 2) and the second segment goes down to z2 = (Db1, 0).In general, for i odd, zi = (∑di/2ej=1 Dtj , 2) and for i even, zi = (∑i/2l=1Dbl , 0). Animportant property of Z is that it ends at one of the two corners on the rightside of R. This is because∑j Dtj = S/2 =∑lDbl .Lemma 2 shows that we can partition each triangle created by the zig-zagZ into triangles whose areas are the corresponding entries in At or Ab. It relies62323393223424793(c) (d)(b)2 3 2 4323932342793(a)A2 3 2 4233242932.66 2.667.98 6.200.34 0.341.02 0.80AtAbz1 z3z0 z2 z424.66 15.64 10.2011.36 19.14Figure 5: (a) Illustration for A,At and Ab, where k = 2 and λ ≈ 0.886. (b) The zigzag pathZ. We have distorted the aspect ratio of the figure to increase readability. (c) The subdivisionof triangles, where Z is shown in red, and (d) the complete cartogram.on the following lemma which is a consequence of properties of barycentriccoordinates. However, we include a proof here because later variants of thelemma would require generalizing this proof.Lemma 1 (Triangle Lemma). Let 4abc be a triangle and let α, β, γ be non-negative numbers, where α+ β + γ = Area(4abc). Then we can find a point pin 4abc, where Area(4pbc) = α, Area(4apc) = β, Area(4abp) = γ, in O(1)arithmetic operations.Proof. Let `a be the line such that a triangle with side bc and a corner on `ahas area α. This line intersects segments ab and ac. Let `b be the line suchthat a triangle with side ac and a corner on `b has area β. This line intersectssegments ab and bc. Let qa be the intersection point of segment ab with line `aand let qb be the intersection point of segment ab with line `b. Assume that theorder of points on segment ab is a, qa, qb, b. Now the triangles 4qabc and 4aqbccover the triangle 4abc so that Area(4abc) < α+ β. This contradiction showsthat the order of points on segment ab is a, qb, qa, b. Hence `a and `b intersectin a point p inside of 4abc. This point p has the desired properties.Note that p can be computed with O(1) arithmetic operations. 2Lemma 2. Let A be an m×2 table such that each cell is assigned a non-negativenumber. Let 4abc be a triangle such that the area of 4abc is equal to the sumof the numbers of A. Then A admits a cartogram inside 4abc such that all7cells of A are represented by triangles and the boundary between those trianglesrepresenting cells in the left column and those representing cells in the rightcolumn is a polygonal path connecting point a to some point on the segment bc.Proof. The proof is by induction on m. The case m = 1 is obvious, recallthe example illustrated in Figure 3. If m > 1 we define α =∑1≤i≤m−1Ai,1 +Ai,2, β = Am,1 and γ = Am,2. Using Lemma 1 we find a point p in 4abcthat partitions the triangle into triangles of areas α, β and γ. We keep thetriangles 4apc and 4abp as representatives for Am,1 and Am,2 and constructthe cartogram for the first m − 1 rows of A in the triangle 4pbc by induction.2To partition triangle 4z2j−2, z2j−3, z2j−1, for 1 ≤ j ≤ bm/2 + 1c (wherez−1 = (0, 2) and zm+1 = (S/2, 2) if needed), we appeal to Lemma 2 with A(in the lemma) being the two columns from At whose sum is Dtj . To makeLemma 2 applicable to cases like Dt1 which represents only one column fromAt, we simply add a column of zeros to A. Similarly, we can partition triangle4z2l−1, z2l−2, z2l, for 1 ≤ l ≤ dm/2e.This yields a table cartogram of the (m+1)×n table A+ that is obtained bystacking At on Ab. Note, however, that all triangles representing cells from thelast row of At have a side that equals one of the edges of Z. Symmetrically, alltriangles representing cells from the first row of Ab have a side on Z. Hence byremoving the edge of Z we glue two triangles of area λAk,j and (1−λ)Ak,j intoa 4-gon of area Ak,j . The 4-gons obtained by removing edges of Z are convexbecause they have crossing diagonals. This completes the construction.To complete the proof of Theorem 1, in which R is a w × h rectangle witharea S, we scale the above cartogram by a factor of h/2 vertically and a factorof 2/h horizontally.2.2. Removing DegeneraciesThe construction of the proof of Theorem 1 creates faces of degenerate shape,i.e., some faces may not be perfect quadrangles, as shown in Figure 5(d). Wemodify this construction to avoid the degeneracies. Of course we have to makea stronger assumption on the input: All entries Ai,j of the table are strictlypositive. The first part of the construction remains unaltered.• Determine k and λ such that ∑1≤i≤k−1 Si + λSk = S/2.• Define At and Ab and the two-column sums Dtj and Dbl for these tables.• Compute the zig-zag in the rectangle R of height 2 and width S/2.Let z0, z1, . . . , zn be the corner points of the zig-zag Z. For i even we definez′i = zi + (0, v) and for i odd z′i = zi − (0, v), i.e., z′i is obtained by shifting zivertically a distance of v into R. We will choose this positive value v to obeyinequalities (B1) and (B2) required by the construction, which will be specifiedlater (after Figure 6). However, one can observe that by choosing a sufficiently8v2− 2vδτ(x, 0)(x′, 2− v)z′izi−1 zi+1z′i+1ziz′i−1FiFi−1 Fi+1z′i−1 z′i+1Figure 6: Before and after convexifying z′i. The dashed lines represent the original Z′.small value for v will cause both of those inequalities to be satisfied. Let Z ′ bethe zig-zag with corners z′0, z′1, . . . , z′n. The segment z′i, zi is the leg at z′i. Theunion of all the legs and Z ′ is the skeleton G′ of a partition of R into 5-gons.We refer to the 5-gons with corners zi−1, zi+1, z′i+1, z′i, z′i−1 as Fi. We refrainfrom introducing extra notation for the two 4-gons at the ends of Z ′ and justthink of them as degenerate 5-gons.Lemma 3. A 5-gon in R with vertices (x1, 0), (x3, 0), (x3, v), (x2, 2− v), (x1, v)has the same area x3 − x1 as the triangle with corners (x1, 0), (x3, 0), (x2, 2).Proof. First note that changing the value of x2 (shear) preserves the area ofthe 5-gon and of the triangle. Hence we may assume that x2 = x3. Now let P bethe parallelogram with corners (x1, 0), (x1, v), (x2, 2), (x2, 2−v). Both, the 5-gonand the triangle can be partitioned into the triangle (x1, 0), (x2, 2 − v), (x3, 0)and a triangle that makes a half of P . 2Some of the 5-gons Fi may not be convex. However, concave corners canonly be at z′i+1 or z′i−1. To get rid of concave corners we deal with corners atz′1, z′2, . . . , z′n−1 in this order. At each z′i we may slightly shift z′i horizontallyand bend the leg to rebalance the areas. This can be done so that the concavecorner at z′i is resolved. We then say that z′i has been convexified. Figure 6shows an example of the process.The vertex z′i has a concave corner in at most one of Fi−1 and Fi+1. In thefirst case we move z′i to the right, in the second case, we move z′i to the left. Bysymmetry, we only detail the second case, i.e, z′i has a concave corner in Fi+1.Shifting z′i horizontally keeps the area of Fi invariant. Only the areas of Fi−1and Fi+1 are affected by the shift. By shifting z′i a distance of δ to the left whilekeeping zi at its place the increase in area of Fi+1 is δ(2 − v)/2. To balancethe increase we move zi, the other end of the leg, to the right by an amount τ ,where τv/2 = δ(2− v)/2. To make sure that the corners at z′i after shifting areconvex we choose δ and τ so that the line connecting the new positions of ziand z′i contains the midpoint of z′i−1 and z′i+1. If the new position of zi is (x, 0)and (x′, 2− v) is the midpoint of z′i−1 and z′i+1 then v/(τ + δ) = 2/(x− x′).9pj+1p0 q0qj+1qjpjαβ γpr(b)(a)Figure 7: (a) The α, β and γ partition of F . (b) A final partition of Fi.We do not want the shift of zi to introduce a crossing. We ensure this witha bound on v. For all j, let Tj = Area(Fj). Since the height of the strip is 2,one can infer from Lemma 3 that Tj is also the distance between zj−1 and zj+1before the shift. If τ ≤ Ti+1, then the leg z′i, zi does not intersect leg z′i+2, zi+2.The absolute value of the slope of the leg z′i, zi after convexifying z′i is less thanv/τ . The slope of the leg is also between the slopes of z′i, z′i−1 and z′i, z′i+1.The absolute value of these slopes is larger than (2 − 2v)/(S/2) which is theminimum possible slope of a segment of Z ′ in R. Define T = minj Tj . Hence ifv/T < (2 − 2v)/(S/2) = 4(1 − v)/S, then τ < T . We thus have an inequalitythat we want to be true for v:v ≤ 4TS + 4T. (B1)Observe that convexifying z′i+1 may require a shift of z′i+1 by δ′ (and a compen-sating shift of zi+1 by τ′) after z′i has been convexified. However, if v ≤ 1/4, thenbalancing area and (B1) imply 14T > vτ′ = δ′(2 − v) ≥ δ′ 74 whence δ′ ≤ T/7.This shows that z′i+1 stays on the right side of the old midpoint of z′i−1 and z′i+1so that the corners at z′i stay convex.The next step of the construction is to place equidistant points on each ofthe legs. The segments between two consecutive points on the leg z′i, zi willserve as sides for quadrangles of the quadrangular subdivision of Fi−1 and Fi+1.Specifically, a leg z′i, zi with i odd is subdivided into k − 1 segments of equallength and a leg z′i, zi with i even is subdivided into m − k segments. Recallthat k is the number of rows in At. For the partition of Fi into 4-gons withthe prescribed areas we proceed inductively as in Lemma 2. We again need apartition lemma, as follows.Lemma 4. Consider a convex 5-gon F as shown in Figure 7(a). Let α, β, γ bepositive numbers with α + β + γ = Area(F ). If α > Area(2p0, q0, qj , pj), β >Area(4pj , r, pj+1), γ > Area(4qj , qj+1, r), then there exists p ∈ F such thatα = Area(Dp0, q0, qj , p, pj), β = Area(2pj , p, r, pj+1), γ = Area(2qj , qj+1, r, p).Proof. The assumptions imply that if p exists it has to be in the interior ofthe triangle 4pj , r, qj . The existence follows from Lemma 1. 2To ensure that the conditions for Lemma 4 are satisfied throughout theinductive partition of the regions Fi we need to bound v. Let M = mini,j Ai,j10be the minimum value in the table. Recall that S/2 is the width of R, and they-distance of pj and pj+1 is at most v. Hence vS/2 is a generous upper boundon Area(4pj , r, pj+1), Area(4qj , qj+1, r), and Area(2p0, q0, qj , pj). We ensurethat these areas are less than β, γ, and α respectively by requiringv <2MS(B2)Theorem 2. Let A be an m×n table of non-negative numbers Ai,j. Let R be arectangle of width w and height h such that w · h =∑i,j Ai,j. Then there existsa non-degenerate cartogram of A in R such that every face in the cartogram isconvex. The construction requires O(mn) arithmetic operations.Proof. The steps of the construction are:• Construct the table cartogram with degeneracies.• Compute the bounds and fix an appropriate value for v, compute theskeleton G′ and its regions Fi, and convexify the legs in order of increasingindex.• Subdivide each of the regions Fi into convex 4-gons (and two triangles).• Remove the edges of the zig-zag to get the cells of the middle row asunions of two triangles, which must generate convex quadrangles, sincethese triangles are contained in rectangle R and the common side of apair of triangles connects opposite sides of R.All can be done with O(mn) arithmetic operations. Regarding the degeneracies,however, there is an issue that remains. To break A into At and Ab, we splitrow k so that the last row of At is a λ-fraction of row k from A while the restof this row becomes the first row of Ab. Degeneracies occur if λ = 1. However,rather than splitting row k in this case, we can treat cells of row k as genericcells and assign a section of a leg to each of them. The construction is almostas before. Two details have to be changed. The first partition of each Fi intothree pieces now produces two 4-gons and a 5-gon, while previously we had twotriangles and a 5-gon in this step, as shown in Figure 7(b). The other change isthat we don’t remove zig-zag edges belonging to Z ′ to merge triangles to 4-gonsat the end of the construction. 2Instead of just knowing that there are no degeneracies, it would be nice tohave a lower bound on the feature size, that is the minimum side-length of a4-gon in the table cartogram. The segments subdividing the legs have length atleast v/m. Because these leg segments have length at most v and vS/2 < M (by(B2)), the opposite edges in a generic 4-gon (the blue edges in Figure 7(b)) havelength at least v. However, the triangles whose composition creates the 4-gonsrepresenting cells of row k can have area smaller than M . These triangles mayhave area λˆM where λˆ = min{λ, 1− λ}. This may lead to a very small featuresize. To improve on this, another degree of freedom in the construction can be11used. Instead of breaking each cell Ak,j into a λ and a 1−λ fraction, we can useindividual values λj to define Atk,j = λjAk,j . The choice of the values λj mustsatisfy two conditions: (1)∑j λjAk,j = λSk = λ∑j Ak,j and (2) if λi = 0 andλj = 1 then |i− j| > 1. By choosing most of the λj to be 0 or 1, and avoidingdegeneracies, we may be able to have a substantial improvement in feature size.3. GeneralizationsIn this section we present several generalizations of the results of Section 2.1.We first introduce the concept of cartograms on weighted area. We then showhow to generalize table cartograms to other shapes and surfaces.3.1. Cartograms on Weighted AreaOne direction for generalizations is to use a broader notion of “area”. Thiscan be done by specifying the weight of a region as an integral over some den-sity function w : R→ R+. The density function should have the property thatthe integrals over triangular regions with nonempty interiors exist and are posi-tive. We call such a density function positive. The following lemma generalizesLemma 1, which can be used to generalize the results of Section 2.1 for arbitrarypositive density functions.Lemma 5 (Weighted Triangle Lemma). Let 4abc and w : 4abc→ R+ bea triangle and a positive density function on 4abc, respectively. Let Area(4abc)be the w-weighted area of the triangle 4abc. Given three non-negative real num-bers α, β, γ, where α+β+γ = Area(4abc), there exists a unique point p inside4abc such that Area(4pbc) = α, Area(4apc) = β, and Area(4abp) = γ.Proof. Let ρ be a ray starting at a and intersecting the segment bc. Since w isa positive density function, Areaw(4xbc) is strictly decreasing as x moves froma along ρ. Hence there is a unique point x(ρ) on ρ such that Areaw(4x(ρ)bc) =α. The points x(ρ) for all different ρ trace a simple curve Pa in 4abc thatseparates a from bc. This curve has a point on ab and a point on ac. Similarly,we get a curve Pb that intersects every ray from b to ac at a point x withAreaw(4axc) = β.Let qa and qb be the intersection points of Pa and Pb with segment ab.Assume that the order of points on segment ab is a, qa, qb, b, then the triangles4qabc and 4aqbc cover the triangle 4abc so that Areaw(4abc) < α+ β. Thiscontradiction shows that the order of points on segment ab is a, qb, qa, b. HencePa and Pb intersect at a point p inside of 4abc. This point p has the desiredproperties.Assume that p and p′ are two points with the desired properties. Thenthere is a pair {y, z} among {a, b, c} such that 4(pyz) ⊂ 4(p′yz) and henceAreaw(4pyz) < Areaw(4p′yz). This contradiction proves uniqueness. 2Note that Lemma 5 can be deduced in several other ways, e.g., using theKnaster-Kuratowski-Mazurkiewicz lemma [19] (even for higher dimensions), orin the context of barycentric coordinate systems [20].12(a) (b) (c)pqsrp s p sq r q rα = 0Aα = 1A AFigure 8: (a)–(b) Two zigzag paths Z0 and Z1 such that their endpoints define a continuousinterval on the boundary of 2pqrs that contains r. (c) By the intermediate value theorem,for some α the corresponding zigzag path must hit r.3.2. Cartogram in an arbitrary convex quadrilateralWe show that every table can be represented as a cartogram in any arbitraryconvex quadrilateral with area equal to the sum of the numbers in the table.Theorem 3. Let A be a table with m rows and n columns of non-negativenumbers. Let 2pqrs be an arbitrary convex quadrilateral with area equal to thesum, S, of the numbers of A. Then there exists a cartogram of A in 2pqrs (withdegeneracies).Proof. The proof for the case when 2pqrs is a rectangle can be found fromTheorem 1. We may thus assume that 2pqrs is a convex quadrilateral that isnot a rectangle, as shown in Figure 8(a). We now show that there must exist azigzag path Z that starts at q and ends at r or s (depending on whether n iseven or odd), and realizes the required areas for the intermediate triangles.Note that such a zigzag path Z does not necessarily split A into two equalhalves, rather, the row k of A that determines At and Ab satisfies∑1≤i≤k−1 Si+λSk = αS for some α ∈ (0, 1]. We prove that such a zigzag path exists by usingthe intermediate value theorem, as follows. Without loss of generality assumethat n is even. For each k = 0, 1, . . . ,m, we find the zigzag paths Z0 and Z1by choosing α = 0 and α = 1. Observe that for some k, the end points of Z0and Z1 define a continuous interval on the boundary of 2pqrs that contains r.By the intermediate value theorem, for some α, the corresponding zigzag pathmust hit r. Figures 8(a)–(c) illustrate such a scenario.Given the zigzag path Z, we can continue as in the proof of Theorem 1. 2Note that the proof of Theorem 3 is existential. A natural approach to findthe required value of α would be to use a binary search in the interval [0, 1].However, the running time in this case should depend on the precision requiredto define α. Hence applying a binary search would give only an approximatesolution in practice.3.3. Table Cartograms in a CircleIn this section we show that any table A of size m×n of non-negative weightsadmits a cartogram inside a circle with area equal to the sum of the numbers ofA, where every edge in the cartogram is represented as a circular arc. To provethe existence of such a cartogram, we modify the proof of Lemma 5.13(e)(a) (b) (c) (d)abcabcacabcbabcFigure 9: (a)–(d) Circular triangles. (e) Not a circular triangle.abcxPa(a) (b)xabcFigure 10: (a) The set of circles Cax used to define Sa(t) for 4©abc. (b) The trace Pa ofpoints x forming a circular triangle 4©xbc with area α.A circular triangle 4©abc is (the bounded component of) the intersectionof three closed regions, each of which is the interior or exterior of one of threepairwise intersecting circles. The region is bounded by three circular arcs (calledarms) that pairwise meet at the points a, b, and c (called vertices). Figures 9(a)–(d) are circular triangles, but Figure 9(e) is not since the (shaded) region iscontained in both the interior and exterior of the circle defined by arm ac. Aclosed disc with three vertices on its boundary is a circular triangle, where allthree arms are the arcs of a single circle.For 4©abc, let Cab, Cbc, and Cac be the circles defined by arms ab, bc, andac, respectively. A pair of these circles, say Cab and Cac, intersect at a. Let xbe their additional intersection point (if it is unique), x = a (if Cab is tangentto Cac), or x be any point on Cab that is not contained in arm ab or ac (ifCab = Cac). If a and x are distinct points, let Cax be the set of circles througha and x (see Figure 10(a)). Otherwise (if Cab is tangent to Cac) let Cax be theset of circles C through a such that one of Cab and Cac is in the interior andthe other in the exterior of C.The set Cax defines a set of circular arcs, {C ∩4©abc|C ∈ Cax}, each of whichpartitions 4©abc into two circular triangles. For example (as in Figure 10(a)),if 4©abc is the intersection of C+ab (the closed interior of Cab), C−bc (the closed14exterior of Cbc), and C+ac, then the two circular triangles (for a circle C ∈ Cax)are C+ab∩C−bc∩C± and C+ac∩C−bc∩C±, where C± is the closed interior or exteriorof C that contains arm ab and C± is its closed complement.Let Sa(t) be a function from t ∈ [0, 1] to circular arcs {C ∩ 4©abc|C ∈ Cax}that interpolates between Sa(0) = arm ab and Sa(1) = arm ac, so that thearea of the left partition (in C±) continuously increases from 0 to Area(4©abc).Define Sb(t) and Sc(t) in a similar way.Lemma 6 (Circular Triangle Lemma). Let 4©abc be a circular triangle andlet α, β, γ be non-negative numbers, where α + β + γ = Area(4©abc). Thenthere exists a point p in 4©abc and circular triangles 4©pbc, 4©apc, 4©abp suchthat Area(4©pbc) = α, Area(4©apc) = β, and Area(4©abp) = γ.Proof. The proof is similar to the proof of Lemma 5. We first find the trace Paof a point x inside 4©abc such that Area(4©xbc) = α, as shown in Figure 10(b).Note that the arms bx and cx of 4©xbc are determined by the arcs of Sb andSc that pass through x. Therefore, each ray in Sa can be intersected by Pa atmost once. We define Pb with respect to Sb analogously. In a similar way tothe proof of Lemma 5, we can prove that Pa and Pb intersect at a single pointp such that Area(4©pbc) = α, Area(4©apc) = β, and Area(4©abp) = γ. Notethat each of 4©pbc, 4©apc, and 4©abp is determined by the intersection of theinterior/exterior of three mutually intersecting circles. Therefore, 4©pbc, 4©apc,and 4©abp are circular triangles. 2A plane graph G with n ≥ 3 vertices is called a plane 3-tree if G is atriangulated plane graph, and for n > 3, G has a vertex whose deletion gives aplane 3-tree of n−1 vertices. Let G be an arbitrary plane 3-tree such the internalfaces of G are assigned non-negative weights. Any plane 3-tree admits a straight-line drawing inside a triangle, where the faces are drawn as triangles respectingthe prescribed face weights [21]. One can use Lemma 6 to generalize this resultto circular triangles, i.e., given a circular triangle 4©abc such that Area(4©abc) isequal to the sum of the face weights of G, one can obtain a drawing of G inside4©abc where the faces are drawn as circular triangles respecting the prescribedface weights.Lemma 7. Let G be an arbitrary plane 3-tree such the internal faces of G areassigned non-negative weights. Let 4©abc be a circular triangle with Area(4©abc)equal to the sum of the face weights of G. Then there exists a drawing of G inside4©abc such that each face of G is drawn as a circular triangle with area equal toits prescribed weight.We are now ready prove the main result of this section.Theorem 4. Let A be a table with m rows and n columns of non-negativenumbers. Let C be an arbitrary circle with area equal to the sum of the numbersof A. Then there exists a cartogram of A in C where every face is a circulartriangle.15Proof. Similar to the proof of Theorem 3, we first find the largest index ksuch that the sum of the numbers in rows 1, 2, . . . , k − 1 is less than S/2. Wemay choose λ ∈ (0, 1] such that ∑1≤i≤k−1 Si + λSk = S/2. We then definethe tables At and Ab with respect to row k. We next find a zigzag path inG that divides the circle into circular triangles. Finally, we use Lemma 6 tocompute the cartograms of the columns of At and Ab that correspond to thosecircular triangles, and remove the segments on the zigzag path to merge thecells corresponding to the row k of A. 23.4. Table Cartogram on a SphereIn this section we show that one can compute a cartogram of a table on thesurface of a sphere. The idea is to first construct a cartogram1 of the table on acylinder, and then use the map projection techniques that preserve area [22, 23]to find a cartogram on the surface sphere. There are several well studied areapreserving map projection techniques such as Lambert’s cylindrical equal-areaprojection, Lambert azimuthal equal-area projection, or Hammer-Aitoff Equal-Area Projection. Here we use Lambert’s cylindrical equal-area projection.Lemma 8. Let A be an m × n table of non-negative numbers. Let H be acylinder with surface area equal to the sum of the numbers of A. Then thereexists a cartogram of A on H.Proof. The case when n = 1 is straightforward. Therefore, we assume thatn ≥ 2. Let h be the height and r be the radius of H. If n is even, then we firstcompute a cartogram on a rectangle H of height h and width 2pir in a similarway as in the proof of Theorem 1. Since n is even, the zig-zag path starts andends at the same corner, when we wrap H into a cylinder. However, the verticeson the left side of H may not match the vertices on the right side of H. Sowe merge the leftmost and rightmost triangles formed by the zigzag path in Hand find the cartogram of columns 1 and n of At in the resulting triangle usingLemma 2. This process is shown in Figures 11(a)–(d).If n is odd, we equally divide the leftmost column into two columns andmove one of these columns to the right of A, as shown in Figures 11(e)–(f).We then compute the cartogram, as in the case when n is even, and remove thesegments that separate the divided leftmost column of At, and the (infinitesimal)segments that separate the divided leftmost column of Ab, as in Figures 11(g)and (h).When n is even, the faces are convex quadrilaterals. However, when n is odd,the faces with areas from the leftmost column of A may be concave hexagons,as shown in Figure 11(h). 2We now use Lambert’s cylindrical equal-area projection to find a cartogramof A on the surface of a sphere. Note that this technique only projects the two1This cartogram may have non-convex faces.16(a) (b) (c) (d)(e) (f) (g) (h)3.05.02.01.8... ... ...... ... ...... ... ...... ... ...............1.52.51.00.9 0.92.51.01.5... ... ...... ... ...... ... ...... ... ...............Figure 11: Cylindrical cartogram construction. (a)–(d) n is even, (e)–(h) n is odd. Note thatwhen n is even, the faces are convex quadrilaterals. However, when n is odd, the faces withareas from the leftmost column of A may be concave hexagons.dimensional cartogram on the sphere. Some parts of the sphere, for examplethe poles, will not be covered.A major problem of using an equal area projection to compute cartogramson the surface of a sphere is the distortion of shapes. Therefore, it is worthinvestigating algorithms that can produce aesthetically pleasing cartograms ona sphere.4. Conclusions and Future WorkWe have presented a simple constructive algorithm that realizes any tableinside a rectangle in which each cell is represented by a convex quadrilateralwith its prescribed weight. If all weights are strictly positive, then we can alsoobtain non-degenerate realizations. This method can be further extended torealize any table inside an arbitrary convex quadrilateral, inside a circle usingcircular arcs, or even on the surface of a sphere. From a practical point of view,the cartograms obtained by our method may not be visually pleasing, but byusing additional straightforward heuristics that improve the visual quality whilekeeping the areas the same, we can obtain cartograms of practical relevance, asshown in Figure 1 and Figure 4. Our theoretical solution plays a vital rolein this context, since heuristics used directly may get stuck, being unable toobtain the correct areas. Whether there exists a method that can graduallychange the areas to provably obtain the correct areas remains an interestingopen problem. It would also be interesting to examine table cartograms forother types of tables, such as triangular or hexagonal grids. From a theoreticalpoint of view, finding algorithms for table cartograms on a sphere with lessdistortion, and generalizing our result to 3D table cartograms (inside a box) arefurther interesting open problems.17AcknowledgmentsInitial work on this problem began at Dagstuhl Seminar 12261 “Putting Dataon the Map” in June 2012 and most of the results of this paper were obtained atthe Barbados Computational Geometry workshop in February 2013. We wouldlike to thank the organizers of these events, as well as many participants forfruitful discussions and suggestions.DedicationWe fondly remember our interactions with Ferran Hurtado. His keen interestand enjoyment in geometric problems inspired an increased pleasure in workingin this area.References[1] W. S. Evans, S. Felsner, M. Kaufmann, S. G. Kobourov, D. Mondal, R. I.Nishat, K. Verbeek, Table cartograms, in: Proceedings of the 21st AnnualEuropean Symposium on Algorithms (ESA), Vol. 8125 of LNCS, Springer,2013, pp. 421–432.[2] E. Raisz, The rectangular statistical cartogram, Geographical Review 24 (2)(1934) 292–296.[3] M. van Kreveld, B. Speckmann, On rectangular cartograms, ComputationalGeometry: Theory and Applications 37 (3) (2007) 175–187.[4] R. Heilmann, D. A. Keim, C. Panse, M. Sips, Recmap: Rectangular mapapproximations, in: Proceedings of the IEEE Symposium on InformationVisualization (INFOVIS), 2004, pp. 33–40.[5] J. Wood, J. Dykes, Spatially ordered treemaps, IEEE Transactions on Vi-sualization and Computer Graphics 14 (6) (2008) 1348–1355.[6] D. Eppstein, M. J. van Kreveld, B. Speckmann, F. Staals, Improved gridmap layout by point set matching, International Journal of ComputationalGeometry and Application 25 (2) (2015) 101–122.[7] D. Eppstein, E. Mumford, B. Speckmann, K. Verbeek, Area-universal andconstrained rectangular layouts, SIAM Journal on Computing 41 (3) (2012)537–564.[8] M. de Berg, E. Mumford, B. Speckmann, On rectilinear duals for vertex-weighted plane graphs, Discrete Mathematics 309 (7) (2009) 1794–1812.[9] M. Alam, T. Biedl, S. Felsner, M. Kaufmann, S. G. Kobourov, T. Ueckerdt,Computing cartograms with optimal complexity, Discrete & ComputationalGeometry 50 (3) (2013) 784–810.18[10] K.-H. Yeap, M. Sarrafzadeh, Floor-planning by graph dualization: 2-concave rectilinear modules, SIAM Journal on Computing 22 (3) (1993)500–526.[11] M. J. Alam, T. Biedl, S. Felsner, M. Kaufmann, S. G. Kobourov, Propor-tional contact representations of planar graphs, Journal of Graph Algo-rithms and Applications 16 (3) (2012) 701–728.[12] J. A. Dougenik, N. R. Chrisman, D. R. Niemeyer, An algorithm to constructcontinuous area cartograms, The Professional Geographer 37 (1) (1985) 75–81.[13] D. Dorling, Area cartograms: their use and creation, no. 59 in Conceptsand Techniques in Modern Geography, University of East Anglia, 1996.[14] D. A. Keim, S. C. North, C. Panse, Cartodraw: A fast algorithm for gen-erating contiguous cartograms, IEEE Transactions on Visualization andComputer Graphics 10 (1) (2004) 95–110.[15] M. T. Gastner, M. E. J. Newman, Diffusion-based method for producingdensity-equalizing maps, National Academy of Sciences 101 (20) (2004)7499–7504.[16] H. Edelsbrunner, R. Waupotitsch, A combinatorial approach to cartograms,Computational Geometry: Theory and Applications 7 (5–6) (1997) 343–360.[17] D. H. House, C. J. Kocmoud, Continuous cartogram construction, in: Pro-ceedings of the conference on Visualization (VIS), 1998, pp. 197–204.[18] W. Tobler, Thirty five years of computer cartograms, Annals Assoc. Amer-ican Geographers 94 (1) (2004) 58–73.[19] B. Knaster, C. Kuratowski, S. Mazurkiewicz, Ein Beweis des Fixpunkt-satzes fu¨r n-dimensionale Simplexe, Fundamenta Mathematicae 14 (1929)132–137.[20] H. S. M. Coxeter, Introduction to Geometry, 2nd Edition, Wiley, New York,1969.[21] T. C. Biedl, L. E. R. Vela´zquez, Drawing planar 3-trees with given faceareas, Computational Geometry: Theory and Applications 46 (3) (2013)276–285.[22] T. G. Feeman, Portraits of the Earth: A Mathematician Looks at Maps,American Mathematical Society, 2002.[23] J. P. Snyder, Map Projections–A Working Manual, U. S. Geological SurveyProfessional Paper 1935, 1987.19

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.52383.1-0349076/manifest

Comment

Related Items