On a search problem in multidimensional grids

✍ Scribed by Miklós Ruszinkó; Gábor Tardos

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 420 KB
• Volume: 59
• Category: Article
• ISSN: 0378-3758
• DOI: 10.1016/s0378-3758(96)00104-8

✦ Synopsis

A search problem of (3. O. H. Katona was solved earlier by the first author (Ruszinko, J. Statist. Plann. Inference 37 (1993), 371-383) where an unknown point x in a 2-dimensional grid has to he located using queries of type "is x = (xl,x2) ~ a = (al,a2)?". Here a is an arbitrary lattice point and x <~ a means that xi <, ag (i = 1,2). In the present paper we consider the generalization of this problem for arbitrary dimension d.