From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,56525db28240414a
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII-7-bit
Received: by 10.66.84.8 with SMTP id u8mr759044pay.45.1343176080802;
        Tue, 24 Jul 2012 17:28:00 -0700 (PDT)
Received: by 10.66.77.1 with SMTP id o1mr649903paw.29.1343175978575;
        Tue, 24 Jul 2012 17:26:18 -0700 (PDT)
Path: 
 p10ni51027076pbh.1!nntp.google.com!4no2155050pbo.1!news-out.google.com!b9ni51611581pbl.0!nntp.google.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!ctu-peer!news.nctu.edu.tw!goblin1!goblin2!goblin.stu.neva.ru!aioe.org!.POSTED!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Newsgroups: comp.lang.ada
Subject: Re: Efficient Sequential Access to Arrays
Date: Tue, 17 Jul 2012 11:01:59 +0200
Organization: cbb software GmbH
Message-ID: <9s89w8awedu5.r6kl7s7vwvx9$.dlg@40tude.net>
References: <4c86d54d-dfeb-44f1-9638-3c416ea51d74@googlegroups.com>
 <ju2496$988$1@speranza.aioe.org>
 <9b134675-b217-4a62-beb1-8b044029aa61@googlegroups.com>
Reply-To: mailbox@dmitry-kazakov.de
NNTP-Posting-Host: 9A8bJrx4NhDLcSmbrb6AdA.user.speranza.aioe.org
Mime-Version: 1.0
X-Complaints-To: abuse@aioe.org
User-Agent: 40tude_Dialog/2.0.15.1
X-Notice: Filtered by postfilter v. 0.8.2
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Date: 2012-07-17T11:01:59+02:00
List-Id: <comp.lang.ada>

On Mon, 16 Jul 2012 23:40:21 -0700 (PDT), Keean Schupke wrote:

> The real problem is that each element needs to be addressed spatially (say
> as a 2D grid) so that all 4 direct, and 4 diagonal neighbours can be
> quickly found (using indexed-addressing), another is that we need to be
> able to tell if any two elements are in the same group (using disjoint-set
> union-find), and another is that we need to be able to iterate through all
> the members of a group given any element in that group.
> 
> If there is a faster data structure that meets all those requirements, then I am listening.

Depends on details.

k-d trees might be worth looking.

Less known are "pyramid" structures (used in image processing, filtering,
compression).

For image segmenting, e.g. by area growing (8th-neighbourhood), one
sometimes uses recursive elements permutations like (1,1) (1,2) (2,1) (2,2)
(1,3) (1,4) (2,3) (2,4). That allows to perform segmenting in strictly
consequent order visiting each pixel once. I remember it was popular in
PDP-11 days when integer multiplication was indeed expensive.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de