123:. The algorithm for doing this involves finding an approximation to the diameter of the point set, and using a box oriented towards this diameter as an initial approximation to the minimum volume bounding box. Then, this initial bounding box is partitioned into a grid of smaller cubes, and grid points near the boundary of the
115:
It follows in the most general case where no convex hull vertices lie in edges of the minimal enclosing box, that at least 8 convex hull points must lie within faces of the box: two endpoints of each of the two edges, and four more points, one for each of the remaining four box faces. Conversely, if
106:
There must exist two neighbouring faces of the smallest-volume enclosing box which both contain an edge of the convex hull of the point set. This criterion is satisfied by a single convex hull edge collinear with an edge of the box, or by two distinct hull edges lying in adjacent box
101:
published a cubic-time algorithm to find the minimum-volume enclosing box of a 3-dimensional point set. O'Rourke's approach uses a 3-dimensional rotating calipers technique, and is based on lemmas characterizing the minimum enclosing box:
76:
is known. It is based on the observation that a side of a minimum-area enclosing box must be collinear with a side of the convex polygon. It is possible to enumerate boxes of this kind in linear time with the approach called
110:
The other four faces need only contain a point of the convex hull. Again, the points which they contain need not be distinct: a single hull point lying in the corner of the box already satisfies three of these four
55:
of the objects in question. It is straightforward to find the smallest enclosing box that has sides parallel to the coordinate axes; the difficult part of the problem is to determine the orientation of the box.
131:, a small set of points whose optimum bounding box approximates the optimum bounding box of the original input. Finally, O'Rourke's algorithm is applied to find the exact optimum bounding box of this coreset.
138:
25:
116:
the convex hull consists of 7 or fewer vertices, at least one of them must lie within an edge of the hull's minimal enclosing box.
119:
It is also possible to approximate the minimum bounding box volume, to within any constant factor greater than one, in
389:
167:, with the tetrahedron's vertices lying at the vertices (0,0,0), (0,1,1), (1,0,1) and (1,1,0) of the unit cube.
295:
98:
427:
345:(2001), "Efficiently approximating the minimum-volume bounding box of a point set in three dimensions",
278:
203:; Shapira, R. (1975), "Determining the minimum-area encasing rectangle for an arbitrary closed curve",
181:
205:
89:. A C++ implementation of the algorithm that is robust against floating point errors is available.
257:
176:
17:
366:
319:
228:
8:
146:
370:
323:
253:
232:
82:
78:
374:
354:
342:
327:
307:
236:
214:
362:
315:
224:
200:
29:
137:
65:
156:
that of the tetrahedron; for instance, a regular tetrahedron with side length
421:
358:
219:
124:
120:
69:
52:
311:
164:
41:
390:"Matlab implementation of the minimum-volume bounding box algorithm"
128:
394:
33:
51:
It is sufficient to find the smallest enclosing box for the
37:
300:
International
Journal of Computer and Information Sciences
85:
in 1983. The same approach is applicable for finding the
258:"Solving geometric problems with the rotating calipers"
134:
A Matlab implementation of the algorithm is available.
279:"Minimum-area rectangle containing a set of points"
340:
141:The minimum bounding box of a regular tetrahedron
419:
199:
409:
294:
298:(1985), "Finding minimal enclosing boxes",
28:enclosing a set of points. It is a type of
252:
218:
387:
248:
246:
136:
420:
243:
87:minimum-perimeter enclosing rectangle
92:
13:
14:
439:
145:The minimal enclosing box of the
59:
74:minimum-area enclosing rectangle
24:problem is that of finding the
403:
381:
334:
288:
271:
193:
149:is a cube, with side length 1/
1:
187:
26:oriented minimum bounding box
7:
412:, Fig. 1, p. 186.
170:
127:of the input are used as a
10:
444:
182:Minimum bounding rectangle
32:. "Smallest" may refer to
388:Melchior, Samuel (2018).
265:Proc. MELECON '83, Athens
206:Communications of the ACM
177:Smallest enclosing ball
359:10.1006/jagm.2000.1127
142:
22:smallest enclosing box
18:computational geometry
347:Journal of Algorithms
220:10.1145/360881.360919
140:
428:Geometric algorithms
283:Geometric Tools, LLC
277:Eberly, D. (2015),
147:regular tetrahedron
312:10.1007/BF00991005
143:
83:Godfried Toussaint
72:algorithm for the
343:Har-Peled, Sariel
79:rotating calipers
435:
413:
407:
401:
399:
385:
379:
377:
341:Barequet, Gill;
338:
332:
330:
296:O'Rourke, Joseph
292:
286:
275:
269:
267:
262:
250:
241:
239:
222:
197:
162:
161:
155:
154:
93:Three dimensions
443:
442:
438:
437:
436:
434:
433:
432:
418:
417:
416:
410:O'Rourke (1985)
408:
404:
386:
382:
339:
335:
293:
289:
276:
272:
260:
254:Toussaint, G. T
251:
244:
198:
194:
190:
173:
159:
157:
152:
150:
99:Joseph O'Rourke
95:
62:
30:bounding volume
12:
11:
5:
441:
431:
430:
415:
414:
402:
380:
333:
306:(3): 183–199,
287:
270:
242:
213:(7): 409–413,
191:
189:
186:
185:
184:
179:
172:
169:
113:
112:
108:
94:
91:
66:convex polygon
61:
60:Two dimensions
58:
9:
6:
4:
3:
2:
440:
429:
426:
425:
423:
411:
406:
397:
396:
391:
384:
376:
372:
368:
364:
360:
356:
353:(1): 91–109,
352:
348:
344:
337:
329:
325:
321:
317:
313:
309:
305:
301:
297:
291:
284:
280:
274:
266:
259:
255:
249:
247:
238:
234:
230:
226:
221:
216:
212:
208:
207:
202:
196:
192:
183:
180:
178:
175:
174:
168:
166:
148:
139:
135:
132:
130:
126:
122:
117:
109:
105:
104:
103:
100:
90:
88:
84:
80:
75:
71:
67:
57:
54:
49:
47:
43:
39:
35:
31:
27:
23:
19:
405:
393:
383:
350:
346:
336:
303:
299:
290:
282:
273:
264:
210:
204:
195:
163:fits into a
144:
133:
118:
114:
96:
86:
73:
63:
50:
48:of the box.
45:
21:
15:
201:Freeman, H.
125:convex hull
121:linear time
70:linear time
53:convex hull
188:References
165:unit cube
111:criteria.
97:In 1985,
42:perimeter
422:Category
256:(1983),
171:See also
64:For the
375:1542799
367:1810433
328:8311538
320:0824371
237:2079688
229:0375828
158:√
151:√
129:coreset
395:GitHub
373:
365:
326:
318:
235:
227:
107:faces.
34:volume
20:, the
371:S2CID
324:S2CID
261:(PDF)
233:S2CID
81:by
68:, a
46:etc.
38:area
355:doi
308:doi
215:doi
16:In
424::
392:.
369:,
363:MR
361:,
351:38
349:,
322:,
316:MR
314:,
304:14
302:,
281:,
263:,
245:^
231:,
225:MR
223:,
211:18
209:,
44:,
40:,
36:,
400:.
398:.
378:.
357::
331:.
310::
285:.
268:.
240:.
217::
160:2
153:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
