David Madore's WebLog: Comment faire de la géographie algorithmique ?

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

↓Entry #2242 [older| permalink|newer] / ↓Entrée #2242 [précédente| permalien|suivante] ↓

(lundi)

Comment faire de la géographie algorithmique ?

Régulièrement[#], je me pose des questions du style :

  1. Quel est le plus long arc de grand cercle à la surface de la Terre qui soit entièrement dans les terres émergées (resp., qui soit entièrement dans la mer) ? Autrement dit, quelle est la plus longue distance qu'on puisse parcourir sur la terre ferme (resp. dans la mer) en allant tout droit ?
  2. Quel est le grand cercle à la surface de la Terre dont la proportion de terre émergée soit la plus grande possible (resp. la plus faible possible) ? Autrement dit, par où doit-on faire le tour de la Terre si on veut rencontrer le plus possible de terre (resp. le plus possible de mer) ?
  3. Quel est l'hémisphère (découpé par un grand cercle quelconque) de la surface de la Terre qui contienne la plus grande proportion de terre émergée (resp. la plus faible possible — ce sera bien sûr simplement l'autre côté du même grand cercle) ? Autrement dit, si on veut faire le tour de la Terre de façon à mettre le plus de terre d'un côté et le plus de mer de l'autre, comment doit-on s'y prendre ?

(Toutes ces questions assimilent implicitement la Terre à une sphère, qu'on aurait divisée, selon un contour bien défini, en une partie « terres émergées » et une partie « mers ». On pourrait bien sûr raffiner, soit en considérant la terre comme un ellipsoïde oblate[#2].)

On n'aura pas de mal à trouver d'autres questions dans le même genre (et on fera bien attention à distinguer des questions qui peuvent se ressembler subtilement : par exemple j'ai parfois eu du mal à expliquer à des non-mathématiciens la différence entre les deux premières questions que je pose ci-dessus, qui sont pourtant bien distinctes). J'ai envie d'appeler ça collectivement la géographie algorithmique, au croisement de la géométrie algorithmique et de la géographie physique (quoique ça pourrait être de la géographie humaine, aussi : je m'étais demandé ce que vaudrait l'entropie de distribution de la densité de population humaine à la surface de la Terre, ça pourrait aussi s'appeler une question de géographie algorithmique).

Certaines de ces questions trouvent une réponse en ligne. Par exemple la question 3 ci-dessus a sa réponse dans cet article Wikipédia, qui prétend que l'hémisphère de la Terre ayant le plus de terres émergées est celui centré sur Nantes (qui pourrait donc, en un certain sens[#3], se targuer d'être le centre des terres émergées), en faisant lui-même référence à un vieil article du Journal of Geography (auquel je n'ai pas accès, ce qui est d'ailleurs franchement honteux de la part de l'éditeur pour un texte aussi vieux [ajout : on m'a communiqué une copie de l'article, mais en fait il ne dit rien sur la manière dont le calcul a été mené : Geographers have made careful determinations to ascertain which hemisphere contains a larger percentage of land area than any other. It has been found to have its center in western France, near Nantes.]). Et la réponse à la question 1 pour ce qui est de la plus longue distance dans la mer prétend être apportée par cette vidéo YouTube, qui trace une ligne droite entre un point de la côte du Pakistan (du côté de Karachi) et un point de la péninsule du Kamčatka en Russie, en passant par le canal du Mozambique et le passage de Drake, ce qui fait plus de 30000km de mer en ligne droite, c'est indiscutablement impressionnant (et un petit peu difficile à visualiser). On trouve aussi des gens qui prétendent que la plus longue distance sur la Terre ferme relie le Libéria (vers Greenville) à la Chine (du coté de Taizhou), encore que ça a l'air de traverser la mer Morte, donc il reste à décider si celle-ci est un lac ou une vraie mer.

Mais la méta-question que je me pose, c'est : comment les gens qui prétendent avoir la réponse à ce genre de questions ont-ils obtenu la réponse en question ? Et comme je suis mathématicien, forcément, je me demande : ont-ils une preuve d'optimalité (au moins pour une certaine approximation bien définie de la forme de la Terre et de la limite des continents) ?, ou ont-ils simplement essayé de placer plein de grands cercles jusqu'à se dire oh, c'est sûrement ça le mieux qu'on puisse faire ? À vrai dire, je soupçonne fortement le second.

Et j'avoue que si je devais essayer de répondre exactement — et en tout cas plus scientifiquement qu'en essayant plein de possibilités à la main — à une de ces questions, je serais bien embarrassé, même si je sais vaguement, ou du moins j'ai su, me servir de PostGIS (et l'ai utilisé pour des problèmes de ce genre). Par exemple, s'agissant de la question 2, même en admettant que j'arrive, pour un grand cercle donné à calculer la proportion de terres émergées rencontrée sur sa circonférence (ce qui, en principe, si on se donne le contour des continents sous forme d'un énorme polygone, consiste simplement à calculer tous les points d'intersection et à sommer les longueurs qui vont bien), encore faut-il arriver à faire la maximisation correctement : peut-être commencer par placer un million de grands cercles à peu près bien répartis sur la Terre, calculer la proportion de terres émergées de chacun d'eux, puis faire un recuit simulé ou (si on arrive à calculer le gradient) une descente de gradient, en espérant que le million de grands cercles de départ était suffisant pour éviter un faux extremum. Au moins l'espace de recherche n'est que de dimension 2 (pour ce qui est des questions 2 et 3 que je pose ci-dessus, il y a « autant » de grands cercles sur une sphère que de paires de points antipodaux sur la sphère, grâce à la polarité, et de même autant d'hémisphères que de points sur lesquels ils peuvent être centrés ; et pour la question 1, on cherche un couple de points évidemment situés sur les côtes).

Mais si je devais programmer la recherche d'un extremum garanti et démontrablement exact une fois fixé un polygone sur la sphère dont on décrète arbitrairement que c'est ça la forme des continents (par exemple VMAP0), je serais encore plus embarrassé. Je suppose que je ferais quelque chose comme ceci, s'agissant par exemple de la question 2 : prendre un point de départ arbitraire (disons le pôle nord) et son grand cercle polaire (qui serait donc l'équateur), regarder l'intersection de ce dernier avec le polygone des côtes, en déduire à la fois la proportion de terres pour ce grand cercle, mais aussi la plus petite cellule polygonale autour de mon point de départ sur laquelle le grand cercle polaire coupe précisément les mêmes segments du polygone des côtes, cellule sur laquelle j'ai donc une forme simple de la fonction de proportion de terre, puis calculer les cellules adjacentes de la même façon, jusqu'à avoir recouvert la terre par des cellules sur chacune desquelles le grand cercle polaire coupe un certain ensemble de segments du polygone des côtes. Puis, dans chaque cellule, faire l'optimisation exacte, ce qui doit être facile vu que la cellule est polygonale et la fonction à optimiser a une forme simple, et enfin, rassembler l'optimum global, qui sera alors démontrablement le bon (pour peu qu'on a mené les calculs en précision garantie, en encadrant systématiquement les bornes d'erreur, etc.). Ça semble un projet assez monstrueux, et je doute sérieusement que quelqu'un ait fait ça.

À encore plus haut niveau, je peux dire que le problème est décidable en raison du théorème de Tarski sur la décidabilité de la géométrie algébrique réelle (plus un petit argument facile pour expliquer que maximiser une somme de sinus, bien que ce ne soient pas des fonctions algébriques, peut néanmoins se traduire comme une maximisation de fonctions algébriques). Et là ce sera vraiment une réponse de matheux, parce qu'essayer d'appliquer ça pour résoudre une des questions ci-dessus est beaucoup plus désespéré qu'essayer de vider les océans à la petite cuiller.

Je suis donc assez insatisfait par les réponses qu'on peut trouver en ligne à ces problèmes de géographie algorithmique, et je suis sûr qu'il faudrait monter une équipe de recherche à gros budget pour travailler là-dessus (et produire plein de thèses, et d'articles à la con, et de congrès internationaux, etc.).

Mise à jour () : Longest Straight Line Paths on Water or Land on the Earth de Rohan Chabukswar et Kushal Mukherjee est apparu récemment sur l'arXiv.

[#] Bon, en vérité, j'écris cette entrée pour me changer les idées, parce qu'il m'est encore arrivée la même chose dont je me plaignais récemment : comme mon entrée sur les espaces homogènes et isotropes partait dans tous les sens (alors qu'elle-même était destinée à être une entrée courte puisque je n'arrivais pas à en écrire une sur le carré magique de Freudenthal-Tits, elle-même commencée parce que celle sur les octonions devenait interminable), j'ai commencé à en écrire une sur le cas particulier du plan projectif complexe, en me disant que ça au moins c'était un sujet trop étroit pour que ça devienne si long que je n'arrive pas à finir l'entrée, et c'est pourtant de nouveau ce qui s'est produit. (Eh oui, je ne m'étais pas rendu compte de ça, mais comprendre comment sont foutus les plans projectifs réels dans le plan projectif complexe, ce n'est pas si trivial.) [Mise à jour : elle a été publiée ici.]

[#2] La terminologie pour désigner les ellipsoïdes de révolution (ceux dont deux axes ont la même longueur) est un peu confuse : il y a deux cas, selon que les deux axes égaux sont plus longs que le troisième (i.e., qu'on a fait tourner une ellipse autour de son axe mineur, ce qui donne une forme aplatie comme la Terre) ou plus courts (i.e., qu'on a fait tourner une ellipse autour de son axe majeur, ce qui donne une forme allongée comme un ballon de rugby). On trouve différentes paires de termes pour distinguer ces deux cas : oblate/prolate (c'est le plus fréquent en anglais, et un peu rare en français), oblate/oblong (où on fait varier le suffixe plutôt que le préfixe), ou encore aplati/allongé (peut-être plus clair, mais ça ne fait pas très scientifique) ou son équivalent anglais flattened/elongated. Je trouve toujours pénible quand des langues ont des terminologies gratuitement différentes : donc je décrète autoritairement que ces différentes paires de termes pourront être utilisées indifféremment (et on fera bien attention à distinguer prolate et oblong, qui sont synonymes, de oblate, qui est leur antonyme ; on évitera en revanche le mot prolong, dont on ne sait pas bien lequel des deux cas il devrait désigner).

[#3] Mais bon, le barycentre des terres émergées, c'est encore un autre problème dans le même genre : là, une des difficultés consiste à définir ce qu'est un barycentre en géométrie sphérique/elliptique (ou dualement, hyperbolique), et il y a plusieurs concepts concurrents, plus ou moins naturels, dans ce sens : à ce sujet, voir la section 7.4 (the Center of Mass Problem on Two-Point Homogeneous Spaces) du livre d'Alexey Shchepetilov, Calculus and Mechanics on Two-Point Homogeneous Spaces, (Springer / ISBN 978-3-540-35384-3), et, pour un concept parmi d'autres (mais peut-être le plus naturel), le joli article de Galperin, A concept of the mass center of a system of material points in the constant curvature spaces, Comm. Math. Phys. 154 (1993) 63–84, en Open Access ici (spoiler : le concept en question consiste, en pratique, pour la sphère, à faire le barycentre euclidien en trois dimensions et à reprojeter vers la sphère depuis son centre).

↑Entry #2242 [older| permalink|newer] / ↑Entrée #2242 [précédente| permalien|suivante] ↑

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]