Search

One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al.2 introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in ℝ1, specified by linear interpolation in a sequence of τ time stamps, we show that all maximal groups can be computed in O(τ2n4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of α(n) in the running time, where α denotes the inverse Ackermann function. In higher dimensions, we can compute all maximal groups in O(τ2n5logn) time (for any constant number of dimensions), regardless of whether the time stamps of entities are the same or not. We also show that one τ factor can be traded for a much higher dependence on n by giving a O(τn42n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on nand linear dependence on τ. [ABSTRACT FROM AUTHOR]

An unfolding of a polyhedron is a single connected planar piece without overlap resulting from cutting and flattening the surface of the polyhedron. Even for orthogonal polyhedra, it is known that edge-unfolding, i.e., cuts are performed only along the edges of a polyhedron, is not sufficient to guarantee a successful unfolding in general. However, if additional cuts parallel to polyhedron edges are allowed, it has been shown that every orthogonal polyhedron of genus zero admits a grid-unfolding with quadratic refinement. Using a new unfolding technique developed in this paper, we improve upon the previous result by showing that linear refinement suffices. For 1-layer orthogonal polyhedra of genus , we show a grid-unfolding algorithm using only additional cuts, affirmatively answering an open problem raised in a recent literature. Our approach not only requires fewer cuts but yields much simpler algorithms. [ABSTRACT FROM AUTHOR]