Kinetic minimum box is a
kinetic data structure to maintain the
minimum bounding box
In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure a ...
of a set of points whose positions change continuously with time. For points moving in a plane, the
kinetic convex hull A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points. It should be distinguished from dynamic convex hull data structures, which handle points undergoing discrete cha ...
data structure can be used as a basis for a responsive, compact and efficient kinetic minimum box data structure.
2D case
The 2D kinetic minimum box builds on the 2D kinetic convex hull in a manner similar to the
kinetic width data structure which maintains the pair of minimum-distance parallel lines that have the entire point set between them. In this case, since a box consists of two pairs of parallel lines (that are perpendicular to each other), analogy can be made with running two perpendicular kinetic width problems, and the data-structure needs to maintain sets of four points two
antipodal pairs which have perpendicular supporting lines.
In the
dual
Dual or Duals may refer to:
Paired/two things
* Dual (mathematics), a notion of paired concepts that mirror one another
** Dual (category theory), a formalization of mathematical duality
*** see more cases in :Duality theories
* Dual (grammatical ...
view where a point maps to a line , four envelopes (left, right, upper, lower) are computed. The range in x-values of a line segment in one of these envelopes corresponds to the range in the supporting slopes of the corresponding convex hull vertex in the primal view. Thus, an interval where the x-values of the four envelopes lists overlap (which can be obtained by merging the lists) corresponds, in the primal view, to a slope range where all lines parallel and perpendicular to the slopes support the same four convex hull vertices. The minimum box (in terms of area or perimeter) can be easily computed for each slope range and the four vertices thus supported, and then the global minimum box can be found by minimizing over these intervals. This algorithm can be kinetized by maintaining the convex hull in a
kinetic convex hull A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points. It should be distinguished from dynamic convex hull data structures, which handle points undergoing discrete cha ...
data structure, the merge of the four envelope lists in a
kinetic sorted list
A kinetic sorted list is a kinetic data structure for maintaining a list of points under motion in sorted order. It is used as a kinetic predecessor data structure, and as a component in more complex kinetic data structures such as kinetic clos ...
and the boxes in a
kinetic priority queue.
Analysis
The
responsiveness and
compactness
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
of this data structure follow from those of the kinetic convex hull, kinetic sorted list and kinetic priority queue data structures. This is also
efficient since the number of
combinatorially different minimum boxes for points is
The existence of a
local data structure for this problem is an open problem.
References
{{Reflist, refs=
[
{{cite conference , url=http://www.cs.duke.edu/~pankaj/publications/papers/kinetic.pdf, title=Maintaining the Extent of a Moving Point Set , publisher=ACM , accessdate=May 19, 2012 , author1=Agarwal, Pankaj , author2=Guibas, Leonidas J. , author3=Hershberger, John , author4=Eric Veach , year=1997 , conference=SCG
]
Kinetic data structures
Geometric data structures