1-3hit |
Taisuke SHIMAMOTO Tetsuo ASANO
This paper addresses the problem of arranging fewest possible probes to detect a hidden object in a specified region and presents a reasonable scheme for the purpose. Of special interest is the case where an object is a double-sided conic cylinder which represents the shape of the energy distribution of laser light used in the optical network. The performance of our scheme is evaluated by comparing the number of probes to that of an existing scheme, and our scheme shows a potential for reducing the number of probes. In other words, the time for detection is significantly reduced from a realistic point of view.
Myung-Soo KIM Kokichi SUGIHARA
We present an algorithm for computing the Minkowski sum of two surfaces of revolution with parallel axes, each defined as a rotational sweep of a slope-monotone closed curve. This result is an extension of that due to Sugihara et al., where the Minkowski sum for two slope-monotone closed curves in the plane is defined.
This paper presents algorithms for computing the Minkowski sum of two polygons P and Q for a family of problems. For P being convex and Q being monotone, an algorithm is given with O (nm) time and space complexity. For both P and Q being monotone polygons, an O (nm log nm) time algorithm is presented and it is shown that the complexity of the sum is Θ (nmα(min(n,m))) in the worst case, where α() is the inverse of Ackermann's function. Finally, an O ((nm+k)log nm) time complexity algorithm is given when P is monotone and Q is simple, where k in the worst case could be Θ(n2m). The complexity of P Q is shown to be Θ(n2m) in the worst case. Here, m and n denote the number of edges of P and Q, respectively.