Come trovare il simplex N dimensionale più piccolo da un insieme di punti che contiene un dato punto?

Question

Ho cercato su google e stack ma non ho ancora trovato una risposta a questo problema. Continuo a trovare risultati relativi al metodo simplex o ai risultati per trovare il simplex arbitrario più piccolo (cioè i vertici non sono vincolati). Nemmeno posso pensare ad una soluzione analitica.

Dato un insieme di punti N-dimensionali, M, e un arbitrario punto N-dimensionale, q, come faccio a trovare il più piccolo simplex N-dimensionale, S, che contiene q come punto interno se i vertici di S devono essere in M? Sono sicuro che potrei risolverlo con un'ottimizzazione, ma mi piacerebbe una soluzione analitica se possibile. Un algoritmo deterministico sarebbe ok, pure.

mi è stato originariamente usando un approccio K vicini più prossimi, ma poi mi sono reso conto che è possibile che la N + 1 vicini più vicini a q non necessariamente creare un simplex che contiene q.

Grazie in anticipo per qualsiasi assistenza fornita.

Answer 1

Penso che si possa fare O (N^2) usando un processo iterativo molto simile a K-NN, ma forse c'è un modo più efficiente. Questo dovrebbe restituire il simplex minimo in termini di numero di vertici.

Per ogni coordinata i in q, possiamo iterare attraverso tutti gli elementi M, confrontando il q_i e m_i. Selezioneremo i due punti in M che ci danno la minima differenza positiva e la minima differenza negativa. Se ripetiamo questo processo per ogni coordinata, allora dovremmo avere il nostro set minimo S.

Sono in grado di comprendere correttamente il problema?