Core-Sets
S is a set of points in Rd.
Bc,r = ball of radius r centered at point c in Rd
Given S, the minimum enclosing ball of S, MEB(S) is the unique minimum-radius ball containing S.
Let r* be the radius of MEB(S).
A ball Bc,(1+ε)r is said to be a (1+ε)-approximation of MEB(S) if r <= r* and S is a subset of Bc,(1+ε)r
Given ε > 0, a subset X of S is said to be an ε-coreset (corset) of S if S is a subset of Bc,(1+ε)r where Bc,r = MEB(X). In other words X is a coreset if an expansion by a factor (1+ε) of its MEB contains S.
Bc,r = ball of radius r centered at point c in Rd
Given S, the minimum enclosing ball of S, MEB(S) is the unique minimum-radius ball containing S.
Let r* be the radius of MEB(S).
A ball Bc,(1+ε)r is said to be a (1+ε)-approximation of MEB(S) if r <= r* and S is a subset of Bc,(1+ε)r
Given ε > 0, a subset X of S is said to be an ε-coreset (corset) of S if S is a subset of Bc,(1+ε)r where Bc,r = MEB(X). In other words X is a coreset if an expansion by a factor (1+ε) of its MEB contains S.
posted by Gaurav at 7:42 PM
0 Comments:
Post a Comment
<< Home