Ü1-A2) Erfasse alle Punkte in der Reihenfolge, wie sie durch eine raumfüllende Kurve durchlaufen werden (z.B. Hilbert- oder Peano-Kurven). Alternativ auch mit einem mäanderförmigen Durchlauf.
Ü2-A2) Sortiere die Punkte nach der aktuellen Unterteilung, wähle immer die Mitte aus und führe das gleiche mit der "rechten und linken" Punktemenge erneut durch. D.h. bei x,y,x,y,... zunächst alle Punkte nach x-Koordinaten sortieren, die Mitte als Knoten in den Baum aufnehmen. Danach die "linke und rechte" Punktmenge nach y-Koordinaten sortieren und wieder die Mitte als Knoten aufnehmen. z.B.: (1,9), (5,6), (5,3), (2,5), (7,9), (3,3)
1.) nach x-sortiert:
(1,2), (2,5), (3,3), (5,{3,6}), (7,9) -> (3,3) als Wurzel
2.) nach y-sortiert:
(2,5), (1,9) -> (2,5) ist linkes Kind von der Wurzel
(5,3), (5,6), (7,9) -> (5,6) ist rechtes Kind von der Wurzel
3.) ...
Ü4-A1) Beim BSP für Punkte wählt man als Segmente die Mittelsenkrechte auf der Verbindungsgeraden zwischen den beiden Punkten. (Eingabereihenfolge beachten!)
D.h. wenn (1,6) eingefügt wird, passiert noch nichts. Wenn dann z.B. (1,0) eingefügt wird, sind (1,6) und (1,0) zu verbinden und die Mittelsenkrechte auf dieser Geraden bildet das Segment. Fügt man dann (2,7) ein, so liegt es im Bereich mit (1,6), so dass man (1,6) mit (2,7) verbindet und wieder die Mittelsenkrechte als neues Segment aufnimmt.
Es gibt "ein System" nachdem man Trenngeraden zieht: Aufgrund der Eingabereihenfolge liegt in einem Bereich (links oder rechts von einem Segment) immer nur ein Punkt, so dass eindeutig festgelegt ist, welche zu verbinden sind.
Beim BSP-Baum für Punkte stehen die eigentlichen Punkte auch erst in den Blättern. Die Knoten enthalten dann immer Mittelsenkrechten als Segmente.