169:
58:
is an arbitrary positive number. When this is the case, one obtains a linear-time or near-linear time approximation scheme, based on the idea of finding a coreset and then applying an exact optimization algorithm to the coreset. Regardless of how slow the exact optimization algorithm is, for any
34:) results in approximately equal numbers. Many natural geometric optimization problems have coresets that approximate an optimal solution to within a factor of
27:
is a small set of points that approximates the shape of a larger point set, in the sense that applying some geometric measure to the two sets (such as their
238:
214:
150:
116:, Mathematical Sciences Research Institute Publications, vol. 52, Cambridge Univ. Press, Cambridge, pp. 1–30,
233:
207:
137:"10. Fast approximate optimization in high dimensions with core-sets and fast dimension reduction"
200:
20:
121:
28:
8:
146:
136:
89:
101:
93:
188:
140:
117:
184:
180:
227:
105:
42:
176:
109:
97:
45:
or near-linear time), and that have size bounded by a function of
31:
168:
88:
65:, the running time of this approximation scheme will be
225:
208:
142:Introduction to HPC with MPI for Data Science
215:
201:
114:Combinatorial and Computational Geometry
134:
226:
98:"Geometric approximation via coresets"
82:
52:independent of the input size, where
239:Algorithms and data structures stubs
163:
72:plus the time to find the coreset.
13:
96:; Varadarajan, Kasturi R. (2005),
14:
250:
167:
41:, that can be found quickly (in
145:. Springer. pp. 259–272.
128:
16:Computational geometry concept
1:
75:
187:. You can help Knowledge by
7:
10:
255:
162:
135:Nielsen, Frank (2016).
234:Computational geometry
183:-related article is a
21:computational geometry
29:minimum bounding box
90:Agarwal, Pankaj K.
196:
195:
152:978-3-319-21903-5
102:Goodman, Jacob E.
94:Har-Peled, Sariel
246:
217:
210:
203:
171:
164:
157:
156:
132:
126:
124:
86:
71:
64:
59:fixed choice of
57:
51:
40:
254:
253:
249:
248:
247:
245:
244:
243:
224:
223:
222:
221:
181:data structures
161:
160:
153:
133:
129:
87:
83:
78:
66:
60:
53:
46:
35:
17:
12:
11:
5:
252:
242:
241:
236:
220:
219:
212:
205:
197:
194:
193:
172:
159:
158:
151:
127:
80:
79:
77:
74:
15:
9:
6:
4:
3:
2:
251:
240:
237:
235:
232:
231:
229:
218:
213:
211:
206:
204:
199:
198:
192:
190:
186:
182:
178:
173:
170:
166:
165:
154:
148:
144:
143:
138:
131:
123:
119:
115:
111:
107:
103:
99:
95:
91:
85:
81:
73:
69:
63:
56:
50:
44:
39:
33:
30:
26:
22:
189:expanding it
174:
141:
130:
113:
84:
67:
61:
54:
48:
37:
24:
18:
106:Pach, János
43:linear time
228:Categories
177:algorithms
110:Welzl, Emo
76:References
112:(eds.),
122:2178310
25:coreset
149:
120:
32:volume
175:This
100:, in
185:stub
147:ISBN
36:1 +
23:, a
179:or
70:(1)
19:In
230::
139:.
118:MR
108:;
104:;
92:;
47:1/
216:e
209:t
202:v
191:.
155:.
125:.
68:O
62:ε
55:ε
49:ε
38:ε
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
