A Good Sampling Method for Guessing Rectangles in [0, 1]²

Masanobu Ohtsuki, Atsushi Minato and Satoru Ozawa

Division of Applied Synergetics, Graduate School of Science and Engineering, Ibaraki University, 4-12-1 Nakanarusawa, Hitachi 316-8511, Japan

(Received March 28, 2000; Accepted June 12, 2000)

Keywords: Rectangle, Learning, Guessing

Abstract. We introduce a good sampling method for guessing the shape of axis parallel rectangles in [0, 1]². We will show that with the algorithm based on that good sampling we can guess the rectangles within worst error O(1/m^2/3),where m is the number of sample points.