{"id":34,"date":"2013-02-17T16:46:59","date_gmt":"2013-02-17T21:46:59","guid":{"rendered":"http:\/\/www.jsylvest.com\/blog\/?p=34"},"modified":"2013-04-26T12:37:05","modified_gmt":"2013-04-26T17:37:05","slug":"computational-cartography-part-1","status":"publish","type":"post","link":"https:\/\/www.jsylvest.com\/blog\/2013\/02\/computational-cartography-part-1\/","title":{"rendered":"Computational Cartography (Part 1)"},"content":{"rendered":"

In the sixth grade my Social Studies teacher lent me a book which had a whole section devoted to alternative maps of the US. What would it look like with a dozen states? Or 200? What if state lines were drawn according to climate and vegetation patterns, or ancestral ethnicities, or any other speculative idea? I'm fascinated by maps generally, and these were no exception.<\/p>\n

Here's a example of a speculative map of the US by Neil Freeman<\/a> that's been making the rounds in the last few days:<\/p>\n

\"The<\/a>
\"Electoral college reform,\" Neil Freeman<\/figcaption><\/figure>\n

My first reaction to seeing this was: Cool. Now how to do I automate this?<\/em> Those two thoughts go together in my head a lot<\/em>. Rather than just idly speculating how to get a machine to do this, I'm actually going to give it a try. Or at least give a try at a first approximation.<\/p>\n

Freeman's method was initialized algorithmically, but a lot of the decisions were subjective. He also uses a lot of data (drainage basins, commuting patterns) that would be too much of a pain for me to track down an integrate for this sort of spare-time project.<\/p>\n

I'm starting by doing everything on a county-by-county basis, which is a useful limit to work with. Without limiting myself to some relatively coarse-grained pre-existing boundaries the computational possibilities would be staggeringly vast, and the result would probably look too foreign anyway. Limiting things to the 3,033 counties and county-equivalents<\/a> (Louisianan\u00a0parishes, Alaskan\u00a0boroughs, Virginian independent cities, ...) will make things more manageable.<\/p>\n

I'll need population data for each county, which I can get from the Census Bureau<\/a>. I'll also need an adjacency graph of counties<\/a>, which I thought would be tricky, but it turns out the Census Bureau has me covered their too. The location of each county is given in that first link. For the final rendering I'll need the shape of each county. Location is simple, but I'll have to do some digging for shape.<\/p>\n

Methods... methods... hmmm.<\/p>\n

A clustering approach seems like a natural way to start. Something like k-means<\/a> where you start with some arbitrary, incorrect centers for each state, and move them around until each state is approximately equally sized. That would at least give you something to refine from.<\/p>\n

K-means is related to Learning Vector Quantization, which was an ancestor of Self-Organizing Maps<\/a>, so that's another direction to explore. I'm not sure how you'd enforce the population similarity complaint off the top of my head. Or, for that matter, how you'd want to encode any of the information in feature space. (This 2011 paper by Skupin and Esperb\u00e9 seems like a solid lead [pdf<\/a>].) I'm not sure how an SOM would work for this but I have a strong feeling there's potential down that road.<\/p>\n

There's definitely a greedy hill-climbing approach that could be easily implemented. Which means there's a Simulated Annealing approach as well. No way of knowing a priori how effective either would be.<\/p>\n

Those techniques — and many others — will need a fitness function. It would be simple enough to write one based on the inequality in state populations. (Ratio of smallest to largest, Gini coefficient, ...) There should be a penalty for non-compact states, perhaps based on perimeter-to-area raio. But that may cause a problem for states along coast lines or rivers. Perhaps use the adjacency graph and penalize states with large diameters, weighted by their actual distance in geographic-space, relative to the number of counties. In any event, Hawaii and Alaska may need special attention for any distance-based rules.<\/p>\n

Genetic Algorithms might come in handy, especially if you already had a reasonable starting point to refine from. How would a chromosome be represented though? Each county is one gene, taking available values of 1-50? The state space would be huge. Something better than the naive approach would be needed.<\/p>\n

I'm sure there are notes in either my Computational Geometry or GIS notebooks that would come in handy. I'll have to flip through those next time I'm in the lab. Maybe my Algorithmic Game Theory notes as well; I seem to remember some relevant problems on siting cell towers that may be adaptable.<\/p>\n

This should give me plenty to get started with. I've got a lot of other irons in the fire, but hopefully in a few days I'll be back with another post laying out my preliminary efforts.<\/p>\n","protected":false},"excerpt":{"rendered":"

In the sixth grade my Social Studies teacher lent me a book which had a whole section devoted to alternative maps of the US. What would it look like with a dozen states? Or 200? What if state lines were … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[10],"tags":[18],"class_list":["post-34","post","type-post","status-publish","format-standard","hentry","category-cs","tag-projects","wpautop"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p3sddF-y","jetpack-related-posts":[{"id":63,"url":"https:\/\/www.jsylvest.com\/blog\/2013\/03\/computational-cartography-gerrymandering\/","url_meta":{"origin":34,"position":0},"title":"Computational Cartography & Gerrymandering","author":"jsylvest","date":"5 March 2013","format":false,"excerpt":"My brief recent dabbling with computational cartography (see Part 1 & Part 2) was inspired by Neil Freeman. His project was initiated as a (speculative) reform to the Electoral College. Incidentally, this is a great idea. Every four years when whichever party looses the White House starts complaining about how\u2026","rel":"","context":"In "CS \/ Science \/ Tech \/ Coding"","block_context":{"text":"CS \/ Science \/ Tech \/ Coding","link":"https:\/\/www.jsylvest.com\/blog\/category\/cs\/"},"img":{"alt_text":"boston-red-sox-world-series-trophy","src":"https:\/\/i0.wp.com\/www.jsylvest.com\/blog\/wp-content\/uploads\/2013\/03\/boston-red-sox-world-series-trophy-200x300.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":1219,"url":"https:\/\/www.jsylvest.com\/blog\/2018\/06\/book-list-2018q1\/","url_meta":{"origin":34,"position":1},"title":"Book List: 2018Q1","author":"jsylvest","date":"7 June 2018","format":false,"excerpt":"Yes, I realize it is now most of the way through the 2nd quarter of the year. Whatever. Here are the books I read in the first three months. Sourdough, Robin Sloan I love technology, and I love baking bread. I'm pretty much right in the cross hairs for target\u2026","rel":"","context":"In "Reviews"","block_context":{"text":"Reviews","link":"https:\/\/www.jsylvest.com\/blog\/category\/reviews\/"},"img":{"alt_text":"Cover of \"Sourdough\" by Robin Sloan","src":"https:\/\/i0.wp.com\/www.jsylvest.com\/blog\/wp-content\/uploads\/2018\/04\/Sloan_Sourdough-200x300.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":1113,"url":"https:\/\/www.jsylvest.com\/blog\/2018\/01\/some-brief-book-reviews-to-close-2017\/","url_meta":{"origin":34,"position":2},"title":"Some brief book reviews to close 2017","author":"jsylvest","date":"4 January 2018","format":false,"excerpt":"A Wild Swan, Michael Cunningham I would think we've saturated the \"modern re-tellings of fairytales, but for adults\" genre, but this was supremely good. They reminded me of Garrison Keillor in the way that some sadness or loss was mixed in to the stories without them being outright tragic. (I've\u2026","rel":"","context":"In "Book List"","block_context":{"text":"Book List","link":"https:\/\/www.jsylvest.com\/blog\/category\/book-list\/"},"img":{"alt_text":"wild-swan","src":"https:\/\/i0.wp.com\/www.jsylvest.com\/blog\/wp-content\/uploads\/2018\/02\/wild-swan-222x300.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":1046,"url":"https:\/\/www.jsylvest.com\/blog\/2017\/07\/what-ive-been-reading\/","url_meta":{"origin":34,"position":3},"title":"What I've Been Reading","author":"jsylvest","date":"25 July 2017","format":false,"excerpt":"Banana: The Fate of the Fruit That Changed the World, Dan Koeppel Not bad. I'm a sucker for this type of history of a single commodity or common household object. It did make we want to try to get my hands on one of the few non-Cavendish cultivars of bananas\u2026","rel":"","context":"In "Book List"","block_context":{"text":"Book List","link":"https:\/\/www.jsylvest.com\/blog\/category\/book-list\/"},"img":{"alt_text":"Banana, Dan Koeppel","src":"https:\/\/i0.wp.com\/www.jsylvest.com\/blog\/wp-content\/uploads\/2017\/06\/71K3llKhVL-200x300.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":703,"url":"https:\/\/www.jsylvest.com\/blog\/2013\/09\/reading-list-for-23-september-2013\/","url_meta":{"origin":34,"position":4},"title":"Reading List for 23 September 2013","author":"jsylvest","date":"23 September 2013","format":false,"excerpt":"Arnold Kling :: Big Gods Here is a question to think about. If religions help to create social capital by allowing people to signal conscientiousness, conformity, and trustworthiness [as Norenzayan claims], how does this relate to Bryan Caplan\u2019s view that obtaining a college degree performs that function? That might explain\u2026","rel":"","context":"In "Reading Lists"","block_context":{"text":"Reading Lists","link":"https:\/\/www.jsylvest.com\/blog\/category\/reading-lists\/"},"img":{"alt_text":"Some sample pilcrows from the H&FJ foundry.","src":"https:\/\/i0.wp.com\/www.jsylvest.com\/blog\/wp-content\/uploads\/2013\/09\/h%2Bfj_pilcrows.gif?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":599,"url":"https:\/\/www.jsylvest.com\/blog\/2013\/06\/some-recent-brief-book-reviews\/","url_meta":{"origin":34,"position":5},"title":"Some recent, brief book reviews","author":"jsylvest","date":"20 June 2013","format":false,"excerpt":"Fairy Tales from the Brothers Grimm, Philip Pullman I knew these were darker than Disney (and everyone else in the 20th C.) would have children believe, but wow. I think there was a stretch of seven stories in a row in which at least one person was casually executed. Cinderella's\u2026","rel":"","context":"In "Reviews"","block_context":{"text":"Reviews","link":"https:\/\/www.jsylvest.com\/blog\/category\/reviews\/"},"img":{"alt_text":"brothers_grimm_pullman_cover","src":"https:\/\/i0.wp.com\/www.jsylvest.com\/blog\/wp-content\/uploads\/2013\/06\/brothers_grimm_pullman_cover-198x300.jpg?resize=350%2C200","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/posts\/34","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/comments?post=34"}],"version-history":[{"count":16,"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/posts\/34\/revisions"}],"predecessor-version":[{"id":376,"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/posts\/34\/revisions\/376"}],"wp:attachment":[{"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/media?parent=34"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/categories?post=34"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.jsylvest.com\/blog\/wp-json\/wp\/v2\/tags?post=34"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}