| Kathi |
Balancierte hierarchische Darstellung
Meine Frage:
Hallo zusammen,
ich soll zeigen in O(nlogn)Schritten, ob ein Punkt in der Ebene in dem Inneren eines konvexen Polygons liegt. Dazu habe ich gegeben ein Polygon P in hierarchischer Darstellung.
Leider verstehe ich noch nicht ganz was sich hinter dieser hierarchische Darstellung verbirgt. Kann mir da jemand helfen?
Meine Ideen:
Die Idee ist, sei Po das erste Polygon mit den Ecken v1_o v2_o... vk_0 k<=4
ich muss nun einen Schwerpunkt konstruiren und dann über die vier entstandenen Sektoren (Halbräume) argumentieren, ob der Punkt in in einem der sektoren liegt. Ich verstehe leider nicht so ganz was damit gemeint ist. |
