抄録
RA-004
Constant-space Data Structure for Farthest-point Voronoi Diagram
浅野哲夫・◎小長谷松雄（北陸先端大）
This paper presents a constant-space data structure for the farthest-point Voronoi diagram for a set of n points in the plane, which is a collection of algorithms for supporting various operations on the diagram using only a constant number of words of O(logn) bits in addition to a read-only array to store the given point set. We show the operations to be supported can be executed in O(n) time without using only constant work space (without using any extra array). This is an extension of our previous results [1, 2, 3, 4].