Top

Published in:

2020 | OriginalPaper | Chapter

4. Computational Geometric Approaches to Equitable Districting: A Survey

Authors : Mehdi Behroozi, John Gunnar Carlsson

Published in: Optimal Districting and Territory Design

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Dividing a piece of land into sub-regions is a natural problem that belongs to many different domains within the world of operations research. There are many different tools that one can use to solve such problems, such as infinite-dimensional optimization, integer programming, or graph theoretic models. In this chapter, we summarize previous methods for solving districting problems that use computational geometry.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Review of Districting Problems in Health Care

next chapter Bounding Procedures and Exact Solutions for a Class of Territory Design Problems

Adjiashvili, D., Peleg, D.: Equal-area locus-based convex polygon decomposition. Theor. Comput. Sci. 411(14–15), 1648–1667 (2010)MathSciNetMATHCrossRef

Anderson, S.P., De Palma, A., Thisse, J.F.: Demand for differentiated products, discrete choice models, and the characteristics approach. Rev. Econ. Stud. 56(1), 21–35 (1989)MathSciNetMATHCrossRef

Aronov, B., Carmi, P., Katz, M.J.: Minimum-cost load-balancing partitions. Algorithmica 54(3), 318–336 (2009)MathSciNetMATHCrossRef

Aurenhammer, F.: Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Comput. Surv. 23(3), 345–405 (1991)CrossRef

Aurenhammer, F., Hoffmann, F., Aronov, B.: Minkowski-type theorems and least-squares clustering. Algorithmica 20(1), 61–76 (1998)MathSciNetMATHCrossRef

Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22(4), 469–483 (1996)MathSciNetMATHCrossRef

Basu, A., Mitchell, J.S., Sabhnani, G.K.: Geometric algorithms for optimal airspace design and air traffic controller workload balancing. J. Exp. Algorithmics 14, 3–31 (2009)MathSciNetMATHCrossRef

Beardwood, J., Halton, J.H., Hammersley, J.M.: The shortest path through many points. Math. Proc. Camb. Philos. Soc. 55(4), 299–327 (1959)MathSciNetMATHCrossRef

Bereg, S.: Orthogonal equipartitions. Comput. Geom. 42(4), 305–314 (2009)MathSciNetMATHCrossRef

10.

Bereg, S., Bose, P., Kirkpatrick, D.: Equitable subdivisions within polygonal regions. Comput. Geom. 34(1), 20–27 (2006)MathSciNetMATHCrossRef

11.

Bespamyatnikh, S., Kirkpatrick, D., Snoeyink, J.: Generalizing ham sandwich cuts to equitable subdivisions. Discret. Comput. Geom. 24(4), 605–622 (2000)MathSciNetMATHCrossRef

12.

Beyer, W.A., Zardecki, A.: The early history of the ham sandwich theorem. Am. Math. Mon. 111(1), 58–61 (2004)MathSciNetMATHCrossRef

13.

Bichot, C.E., Siarry, P. (eds.) Graph Partitioning. Wiley, New York (2011)MATH

14.

Blagojević, P.V., Ziegler, G.M.: Convex equipartitions via equivariant obstruction theory. Isr. J. Math. 200(1), 49–77 (2014)MathSciNetMATHCrossRef

15.

Boyd, T.D., Jameson, M.H.: Urban and rural land division in ancient Greece. Hesperia J. Am. Sch. Class. Stud. Athens 50(4), 327–342 (1981)CrossRef

16.

Brams, S.J., Taylor, A.D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University, Cambridge (1996)MATHCrossRef

17.

Brieden, A., Gritzmann, P.: On optimal weighted balanced clusterings: gravity bodies and power diagrams. SIAM J. Discret. Math. 26(2), 415–434 (2012)MathSciNetMATHCrossRef

18.

Brieden, A., Gritzmann, P., Klemm, F.: Constrained clustering via diagrams: a unified theory and its application to electoral district design. Eur. J. Oper. Res. 263(1), 18–34 (2017)MathSciNetMATHCrossRef

19.

Buot, J., Kano, M.: Weight-equitable subdivision of red and blue points in the plane. Int. J. Comput. Geom. Appl. 28(1), 39–56 (2018)MathSciNetMATHCrossRef

20.

Carlsson, J.G.: Dividing a territory among several vehicles. INFORMS J. Comput. 24(4), 565–577 (2012)MathSciNetMATHCrossRef

21.

Carlsson, J.G., Devulapalli, R.: Dividing a territory among several facilities. INFORMS J. Comput. 25(4), 730–742 (2012)MathSciNetCrossRef

22.

Carlsson, J.G., Armbruster, B., Ye, Y.: Finding equitable convex partitions of points in a polygon efficiently. ACM Trans. Algorithms 6(4), 72 (2010)MathSciNetMATHCrossRef

23.

Carlsson, J.G., Carlsson, E., Devulapalli, R.: Shadow prices in territory division. Netw. Spat. Econ. 16(3), 893–931 (2016)MathSciNetMATHCrossRef

24.

Cortés, J.: Coverage optimization and spatial load balancing by robotic sensor networks. IEEE Trans. Autom. Control 55(3), 749–754 (2010)MathSciNetMATHCrossRef

25.

Didandeh, A., Bigham, B.S., Khosravian, M., Moghaddam, F.B.: Using Voronoi diagrams to solve a hybrid facility location problem with attentive facilities. Inf. Sci. 234(1), 203–216 (2013)MathSciNetMATHCrossRef

26.

Drezner, T., Drezner, Z.: Voronoi diagrams with overlapping regions. OR Spectr. 35(3), 543–561 (2013)MathSciNetMATHCrossRef

27.

Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2(1–4), 153 (1987)MathSciNetMATHCrossRef

28.

Fruchard, A., Magazinov, A.: Fair partitioning by straight lines. In: Adiprasito, K., Bárány, I., Vilcu, C. (eds.) Convexity and Discrete Geometry Including Graph Theory. Springer Proceedings in Mathematics and Statistics, vol. 148, pp. 161–165. Springer, Cham (2016)CrossRef

29.

Galvão, L.C., Novaes, A.G., De Cursi, J.S., Souza, J.C.: A multiplicatively-weighted Voronoi diagram approach to logistics districting. Comput. Oper. Res. 33(1), 93–114 (2006)MATHCrossRef

30.

Geiß, D., Klein, R., Penninger, R., Rote, G.: Reprint of: optimally solving a transportation problem using Voronoi diagrams. Comput. Geom. 47(3), 499–506 (2014)MathSciNetMATHCrossRef

31.

Hill, T.P.: Determining a fair border. Am. Math. Mon. 90(7), 438–442 (1983)MathSciNetMATHCrossRef

32.

Ito, H., Uehara, H., Yokoyama, M.: 2-dimension ham sandwich theorem for partitioning into three convex pieces. In: Akiyama, J., Kano, M., Urabe, M. (eds.) Discrete and Computational Geometry: Japanese Conference on Discrete and Computational Geometry (JCDCG 1998). Lecture Notes in Computer Science, vol. 1763, pp. 129–157. Springer, Berlin (2000)CrossRef

33.

Kaneko, A., Kano, M.: Balanced partitions of two sets of points in the plane. Comput. Geom. 13(4), 253–261 (1999)MathSciNetMATHCrossRef

34.

Karasev, R., Hubard, A., Aronov, B.: Convex equipartitions: the spicy chicken theorem. Geom. Dedicata 170(1), 263–279 (2014)MathSciNetMATHCrossRef

35.

Kinsey, L.C.: Topology of Surfaces. Springer, New York (1993)MATHCrossRef

36.

Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: Bansal, N., Finocchi, I. (eds.) Algorithms—ESA 2015. Lecture Notes in Computer Science, vol. 9294, pp. 865–877. Springer, Berlin (2015)MATHCrossRef

37.

Nandakumar, R.: Fair Partitions (2018). http://nandacumar.blogspot.com/2006/09/cutting-shapes.html. Accessed 1 July 2018

38.

Ogilvy, C.S.: Excursions in Geometry. Dover, Mineola (1990)MATH

39.

Okabe, A., Suzuki, A.: Locational optimization problems solved through Voronoi diagrams. Eur. J. Oper. Res. 98(3), 445–456 (1997)MATHCrossRef

40.

Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edn. Wiley, Chichester (2000)MATHCrossRef

41.

Paterson, M.S., Yao, F.F.: Efficient binary space partitions for hidden-surface removal and solid modeling. Discret. Comput. Geom. 5(5), 485–503 (1990)MathSciNetMATHCrossRef

42.

Pavone, M., Arsie, A., Frazzoli, E., Bullo, F.: Distributed algorithms for environment partitioning in mobile robotic networks. IEEE Trans. Autom. Control 56(8), 1834–1848 (2011)MathSciNetMATHCrossRef

43.

Pavone, M., Frazzoli, E., Bullo, F.: Adaptive and distributed algorithms for vehicle routing in a stochastic and dynamic environment. IEEE Trans. Autom. Control 56(6), 1259–1274 (2011)MathSciNetMATHCrossRef

44.

Reitsma, R., Trubin, S., Mortensen, E.: Weight-proportional space partitioning using adaptive Voronoi diagrams. Geoinformatica 11(3), 383–405 (2007)CrossRef

45.

Sakai, T.: Radial partitions of point sets in R ². In: Proceedings of the Japan Conference on Discrete and Computational Geometry ’98 (Collection of Extended Abstracts), pp. 74–78. Tokai University, Tokyo (1998)

46.

Schumacker, R.A., Brand, B., Gilliland, M.G., Sharp, W.H.: Study for applying computer-generated images to visual simulation. Technical report AFHRL-TR-69-14, US Air Force Human Resources Lab, Brooks Air Force Base, USA (1969)

47.

Segal-Halevi, E., Nitzan, S., Hassidim, A., Aumann, Y.: Fair and square: cake-cutting in two dimensions. J. Math. Econ. 70(1), 1–28 (2017)MathSciNetMATHCrossRef

48.

Shamos, M.I., Hoey, D.: Closest-point problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pp. 151–162. IEEE, Berkeley (1975)

49.

Smith, W.D., Wormald, N.C.: Geometric separator theorems and applications. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 232–243. IEEE Computer Society, Washington (1998)

50.

Soberón, P.: Gerrymandering, sandwiches, and topology. Not. AMS 64(9), 1010–1013 (2017)MathSciNetMATH

51.

Svec, L., Burden, S., Dilley, A.: Applying Voronoi diagrams to the redistricting problem. UMAP J. 28(3), 313–329 (2007)

52.

Weisstein, E.W.: Ham sandwich theorem. In: MathWorld—A Wolfram Web Resource (2018). http://mathworld.wolfram.com/HamSandwichTheorem.html. Accessed 1 July 2018

53.

Xue, M.: Airspace sector redesign based on Voronoi diagrams. J. Aerosp. Comput. Inf. Commun. 6(12), 624–634 (2009)CrossRef

54.

Ziegler, G.M.: Cannons at sparrows. Eur. Math. Soc. Newsl. 95, 25–31 (2015)MathSciNetMATH

Title: Computational Geometric Approaches to Equitable Districting: A Survey
Authors: Mehdi Behroozi
John Gunnar Carlsson
Publisher: Springer International Publishing
Book: Optimal Districting and Territory Design
Print ISBN: 978-3-030-34311-8

Electronic ISBN: 978-3-030-34312-5

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-34312-5_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"