Qual è il modo più semplice per verificare se un punto P si trova all'interno di uno scafo convesso formato da un insieme di punti X?Trova se un punto è all'interno di uno scafo convesso per un insieme di punti senza calcolare lo scafo stesso
Vorrei un algoritmo che funzioni in uno spazio ad alta dimensione (ad esempio, fino a 40 dimensioni) che non calcoli esplicitamente lo scafo convesso stesso. Qualche idea?
Non è necessario calcolare lo scafo convesso stesso, poiché sembra piuttosto problematico negli spazi multidimensionali. C'è un well-known property of convex hulls:
Qualsiasi vettore (punto) v interno convesso dei punti [v1, v2, .., vn] può essere presentato come sum(ki*vi), dove 0 <= ki <= 1 e sum(ki) = 1. Corrispondentemente, nessun punto al di fuori dello scafo convesso avrà tale rappresentazione.
Nello spazio m-dimensionale, questo ci darà l'insieme di m equazioni lineari con n incognite.
modificare
io non sono sicuro circa la complessità di questo nuovo problema nel caso generale, ma per m = 2 sembra lineare. Forse, qualcuno con più esperienza in quest'area mi correggerà.
In realtà nello spazio m-dimensionale hai bisogno di m + 1 punti a causa del teorema di Carathéodory: http://en.wikipedia.org/wiki/Carathéodory's_theorem_(convex_hull) La difficoltà è trovareind che m + 1 punti funzionano. – lhf
@lhf Questa è una buona nota, anche se non influisce sulla correttezza della risposta (e non è chiaro come applicarla alla risoluzione di tali equazioni). –
Il problema è che l'algebra lineare ti darà facilmente uno spazio dimensionale n-m di soluzioni alla tua equazione, ma non ti dà alcun modo semplice per soddisfare anche le disuguaglianze. Quindi il teorema che citi è un buon modo per mostrare che un punto è all'interno dello scafo convesso di m + 1 punti, ma per un insieme più grande di punti devi trovare il giusto insieme di m + 1 punti per usare il teorema . Ci sono n scegli m + 1 tali set da provare. In 40 dimensioni questo sarà un problema. – btilly
Sei disposto ad accettare una risposta euristica che di solito dovrebbe funzionare ma non è garantita? Se sei allora potresti provare questa idea a caso.
Sia f (x) il cubo della distanza a P per il numero di elementi in X, meno la somma dei cubi della distanza a tutti i punti in X. Inizia da qualche parte in modo casuale e usa una collina algoritmo di arrampicata per massimizzare f (x) per x in una sfera molto lontana da P. Ad eccezione dei casi degenerati, se P non è nello scafo convesso questo dovrebbe avere una buona probabilità di trovare la normale in un iperpiano che P è su un lato di, e tutto in X è dall'altra parte di.
Il punto si trova all'esterno dello scafo convesso degli altri punti se e solo se la direzione di tutti i vettori da esso a quegli altri punti si trova su meno della metà di un cerchio/sfera/ipersfera attorno ad esso.
Sembra una buona soluzione' O (m * n^2) '!+1 –
Sul secondo però, questa proprietà sarà difficile da controllare per le dimensioni 'm'. Non è più facile che risolvere equazioni lineari di 'm'. –
questo è in realtà un ottimo algoritmo. Per controllare "su meno di 1/2 di un'ipersfera" controlli il prodotto punto tra le due direzioni e vedi se 2 sono negative (cioè in direzione opposta). o mi sono perso qualcosa? –
Il problema può essere risolto trovando un punto possibile di un programma lineare. Se sei interessato ai dettagli completi, invece di collegare semplicemente un LP a un risolutore esistente, ti consiglio di leggere il capitolo 11.4 in Boyd and Vandenberghe's excellent book on convex optimization.
Set A = (X[1] X[2] ... X[n]), vale a dire, la prima colonna è v1, il secondo v2, ecc
risolvere il seguente problema LP,
minimize (over x): 1
s.t. Ax = P
x^T * [1] = 1
x[i] >= 0 \forall i
dove
x^T è la trasposizione di x[1] è il vettore tutto-1.Il problema ha una soluzione se il punto è nello scafo convesso.
Ci sono delle implementazioni in giro? Sto attraversando un periodo molto difficile per costruire questo codice. –
Quale solutore LP usi? http://lpsolve.sourceforge.net/5.5/ è un solutore LP open source che è abbastanza semplice da usare. EDIT: non ha capito che stai cercando l'intera shebang; Sfortunatamente non conosco alcun pacchetto di questo tipo. – user1071136
In realtà sto programmando questo nel browser, quindi attualmente sto usando http://numericjs.com/documentation.html - Sto solo avendo problemi a trasformare le disuguaglianze. C'è qualche esempio qui http://www.joyofdata.de/blog/testing-linear-separability-linear-programming-r-glpk/ ma non ho familiarità con R o così sto ancora avendo problemi! –
Ho avuto lo stesso problema con 16 dimensioni.Dal momento che anche qhull non ha funzionato correttamente poiché sono stati generati troppi visi, ho sviluppato il mio approccio testando se è possibile trovare un iperpiano di separazione tra il nuovo punto ei dati di riferimento (che io chiamo "HyperHull";)) .
Il problema di trovare un iperpiano di separazione può essere trasformato in un problema di programmazione quadratica convesso (vedere: SVM). L'ho fatto in Python usando cvxopt con meno di 170 righe di codice (incluso I/O). L'algoritmo funziona senza modifiche in nessuna dimensione, anche se esiste il problema, che quanto più alta è la dimensione tanto maggiore è il numero di punti sullo scafo (vedi: On the convex hull of random points in a polytope). Poiché lo scafo non è costruito in modo esplicito ma controllato, se un punto è all'interno o meno, l'algoritmo presenta vantaggi molto grandi in dimensioni maggiori rispetto ad es. Scafo rapido.
Questo algoritmo può essere "naturalmente" parallelizzato e l'accelerazione dovrebbe essere uguale al numero di processori.
Se potessi mettere in atto la tua implementazione o parte di essa su github sarebbe molto apprezzato, da molte persone Credo (http://www.mathworks.com/matlabcentral/answers/77363-very-high-dimensional-convex-hulls). Forse per te sembra molto semplice. – j13r
Anche se il post originale era tre anni fa, forse questa risposta sarà ancora di aiuto. L'algoritmo Gilbert-Johnson-Keerthi (GJK) trova la distanza più breve tra due politopi convessi, ognuno dei quali è definito come lo scafo convesso di un insieme di generatori --- in particolare, lo stesso scafo convesso non deve essere calcolato. In un caso particolare, come viene richiesto, uno dei politopi è solo un punto. Perché non provare a utilizzare l'algoritmo GJK per calcolare la distanza tra P e lo scafo convesso dei punti X? Se quella distanza è 0, allora P è dentro X (o almeno sul suo confine). Un'implementazione GJK in Octave/Matlab, denominata ClosestPointInConvexPolytopeGJK.m, insieme al codice di supporto, è disponibile allo http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html. Una semplice descrizione dell'algoritmo GJK è disponibile in Sect. 2 di un documento, allo http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf. Ho usato l'algoritmo GJK per alcuni set X molto piccoli nello spazio tridimensionale e ho avuto buoni risultati. Il modo in cui le prestazioni di GJK sono paragonabili ai metodi di programmazione lineare che altri raccomandano è incerto (anche se qualsiasi confronto sarebbe interessante). Il metodo GJK evita di calcolare lo scafo convesso, o di esprimere lo scafo in termini di disuguaglianze lineari, che potrebbero richiedere molto tempo. Spero che questa risposta aiuti.
C'è una ragione particolare per cui vuoi farlo? Il calcolo dello scafo convesso non è molto costoso (O (n lg n)) e semplifica enormemente il problema. – templatetypedef
@templatetypedef: Il calcolo dello scafo convesso non è molto costoso in 2 dimensioni. Ma diventa esponenzialmente più costoso man mano che aumenti il numero di dimensioni. Non vuoi farlo per un problema di 40 dimensioni. – btilly
Forse questa domanda sarebbe più adatta a [mathoverflow] (http://mathoverflow.com)? – wich