• Create Account

#Actualmax343

Posted 13 November 2012 - 07:59 PM

It seems I was wrong. This problem can be solved in linear expected time.
This simple (general position) algorithm should do the trick:

FindMinSphere(S, origSphereVerts)
1. sphereVerts = origSphereVerts, remainingVerts = empty
2. for each i[k] in random pi(1,2,...,length(S))
2.1 if S[i[k]] is not contained in the sphere spanned by sphereVerts
2.1.1 sphereVerts = FindMinSphere(remainingVerts, EliminateExtraVertex(origSphereVerts + S[i[k]]))
2.2 remainingVerts += S[i[k]]
3. return sphereVerts

EliminateExtraVertex(S)
1. X=S
2. if length(S)==5
2.1 X = from the 5 possible spheres in X choose the one that contains all five points
3. return X


#1max343

Posted 13 November 2012 - 07:58 PM

It seems I was wrong. This problem can be solved in linear expected time.
This simple (general position) algorithm should do the trick:

FindMinSphere(S, origSphereVerts)
1. sphereVerts = origSphereVerts, remainingVerts = empty
2. for each i(k) in random pi(1,2,...,length(S))
2.1 if S(i(k)) is not contained in the sphere spanned by sphereVerts
2.1.1 sphereVerts = FindMinSphere(remainingVerts, EliminateExtraVertex(origSphereVerts + S(i(k))))
2.2 remainingVerts += S(i(k))
3. return sphereVerts

EliminateExtraVertex(S)
1. X=S
2. if length(S)==5
2.1 X = from the 5 possible spheres in X choose the one that contains all five points
3. return X


PARTNERS