Konvexe Hüllen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:30 Di 07.12.2004 | | Autor: | BigFella |
Hallo zusammen,
vielleicht hat ja jemand eine schlaue Idee, und zwar:
Also ich weiß, dass ein Punkt in der konvexen Hülle von anderen Punkten liegt, aber wie kann man nun am besten die konvexkombination bestimmen? Gibts da einen schlauen algorithmus?
Viele Grüße!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:36 Di 07.12.2004 | | Autor: | Marc |
Hallo BigFella!
> Also ich weiß, dass ein Punkt in der konvexen Hülle von
> anderen Punkten liegt, aber wie kann man nun am besten die
> konvexkombination bestimmen? Gibts da einen schlauen
> algorithmus?
Was meinst du denn mit Konvexkombination?
Meinst du vielleicht folgendes:
P sei in der konvexen Hülle von [mm] $M=\{P_1,P_2,\ldots\}$
[/mm]
Gesucht ist i und j, so dass P auf der Verbindungsstrecke [mm] $\overline{P_i P_j}$ [/mm] liegt (bzw. so dass [mm] $t\in[0,1]$ [/mm] existiert mit [mm] $P=t*P_i+(1-t)*P_j$).
[/mm]
Aus welchem Vektorraum V stammen denn die Punkte?
Ist M endlich?
Ich nehmen mal an, dass [mm] $V=\IR^3$ [/mm] und $|M|=n$
Eine Idee wäre, die n Vektoren [mm] $\overrightarrow{PP_i}$, $i=1,\ldots,n$ [/mm] zu bestimmen und diese Menge dann die linear abhängigen zu gruppieren.
Aber das ist genauso aufwendig wie für alle Punktepaare die Verbindungsstrecke zu bilden und die Punktprobe mit P durchzuführen (Aufwand [mm] $O(n^2)$).
[/mm]
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:52 Di 07.12.2004 | | Autor: | BigFella |
also gestern Abend war ich dann doch etwas zu müe um das genau zu schreiben als hier nochmal genauer:
gegeben p, [mm] q_{1},..,q_{n} \in \IR^{d} [/mm] (d gross). Die konvexe Hülle der q nun direkt auszurechnen ist etwas schwer bzw sehr aufwendigund: Quickhull algorithmus scheint da nur bis d ungefähr 10 wirkich machbar zu sein. Gut ich suche aber für p nun eine Darstellung p [mm] =\sum_{i}^{n} x_{i}p_{i} [/mm] mit [mm] \sum_{i}^{n}x_{i}=1. [/mm] Wenn die konvexe Hülle ein Simplex ist, also d=n ok, aber was mache ich wenn n >> d? Gibts dafür einen guten Algorithmus?
|
|
|
|
