Abstract | ||
---|---|---|
Abstract. Computing visible information, such as a visible surface de- termination, is a significant problem and has been mainly studied in the fields of computational geometry and/or computer graphics[2, 4,6,10,11, 13]. Furthermore, recently, one might be attracted to problems for deal- ing with continuously moving objects in a geometrical space [1,9,12, 14]. In this paper, we propose two indexing methods, called an Mutual Visible Intervals search tree (MVI-tree) and an Mutual Visible Intervals search list (MVI-list). Using each index, one can efficiently find “mu- tual visible-surfaces” of two moving objects from a query time. “Mutual visible surfaces” are subregions which are “visible” each other. We give algorithms for constructing an MVI-tree and an MVI-list from a set M of two convex polygons M0 with n0 vertices and M1 with n1 vertices, in the case where every convex polygon moves by uniform motion. An MVI- tree of M can be constructed in time O(N log N) using space O(N) and an MVI-list of M can be constructed in time O(N) using space O(N), where N is the total number,of vertices and N = n0 + n1. “Mutual vis- ible intervals”, i.e. “one-dimensional mutual visible surfaces”, of M at a query time can be found in time O(log N) using an MVI-tree or an MVI-list. Keyword Spatio-Temporal Index, Visible Surface Determination, Mu- tual Visible Intervals, Moving Object, MVI-tree, MVI-list |
Year | Venue | Keywords |
---|---|---|
2007 | WALCOM | indexation,computer graphic |
Field | DocType | Citations |
Binary logarithm,Discrete mathematics,Combinatorics,Polygon,Vertex (geometry),Computational geometry,Convex polygon,Regular polygon,Time complexity,Mathematics,Search tree | Conference | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yoshiyuki Kusakari | 1 | 10 | 3.34 |
Yuta Sugimoto | 2 | 0 | 0.34 |
Junichi Notoya | 3 | 0 | 0.34 |
Masao Kasai | 4 | 0 | 0.34 |