[Talk-de] Algorithmus für effiziente PLZ-Gebiete gesucht

[Marcus Wolschon]

2009/10/26 Tobias Wendorff <tobias.wendorff at uni-dortmund.de>:
> Am Mo, 26.10.2009, 14:16 schrieb Philipp Matthias Hahn:
>
>> Und jetzt bitte nicht dir Frage, was ein "Algorithmus" oder eine
>> "konvexe Hülle" ist :-)
>
> Nein, nein ;-)
>
> Ich habe aufgrund der Überschneidungen nur noch nie konvexe Hüllen,
> sondern fasst immer nur Thiessen verwendet.

An Voronoi-Diagramme hab ich schon gedacht. Mittels des Divide and
Conquer -Ansatzes sollte das gut zu parallelisieren sein. Nur wie macht
man das ohne einen großteil aller Punkte welche eine PLZ haben mehrfach
in den Speicher zu laden oder gleich nochmal Speicher in der Größenordnung
dieser Punktmenge zu benötigen?
Die alternative Berechnung über die untere Konvexe Hülle hat die Konvexe
Hülle bereits als Teilschritt bevor nochmal eine teure O(n)-Transformation
gemacht wird.
Sweep meine ich, scheidet völlig aus wegen der Sortierung. Da lass ich
mich aber gerne von Leuten mit mehr Erfahrung in PostGIS (der eingesetzten
Datenbank) korrigieren. Dann die einen spatial-Index von Points für eine
Sortierung eines Suchergebnisses nach der Lat-Achse nutzen wenn die
Suche über ein String-Feld geht (also nicht über den Index selbst gesucht wird)?

Marcus