[R-sig-Geo] existance of a specific non-overlapping marked spatial model in spatstat or other R package?

[Nicholas Lewin-Koh]

Hi,
I don't think the code exists, but I think that there are modifications
of the 
algorithm Rolf described that may be much faster. I assume the
predetermined
set of marks is a set of distinct classes with different radii. 
One thing that comes to mind is you may want to generate the marks first
and
then assign locations. So if you allocate the largest radii first, you
may be able to
sequentially eliminate whole regions of the space where the next disk
could be allocated
using a quad tree, and there by do fewer rejections of locations. There
may be some
divide and conquer type strategies that work as well. 

Thinking about this more, it seems like the most time consuming step
would be the 
acceptance/rejection of new locations because of the search for adjacent
intersecting discs.
So as the plane fills up there will be more and more rejections, and the
search time will increase. 
In fact for a finite area, there will be an upper bound on the number of
points depending on
the distribution of marks. Which suggest that one would want to first
generate the marks, and check that the
sum of the disks is less than the total area of your region.

So as I am musing here, and probably getting less and less helpful, I am
thinking that 
using the delaunay triangulation or the nearest neighbor graph might
help speed up the search.
I am also wondering if one could condition on the existing points more
efficiently, may
be using some sort of metropolis hastings type algorithm to ensure that
the next draw
is closer to the restricted space available. I am even guessing there
may be some percolation
model that would approximate this process and be faster to generate.

Ok used up my 2c. Hope this helps

Nicholas
 

   

> Date: Fri, 28 May 2010 10:00:35 +1200
> From: Rolf Turner <r.turner at auckland.ac.nz>
> To: Quets Jan <Jan.Quets at ua.ac.be>
> Cc: "r-sig-geo at stat.math.ethz.ch" <r-sig-geo at stat.math.ethz.ch>
> Subject: Re: [R-sig-Geo] existance of a specific non-overlapping
> 	marked	spatial model in spatstat or other R package?
> Message-ID: <B9268B92-B6F4-420C-AF04-EEE1DA182F67 at auckland.ac.nz>
> Content-Type: text/plain; charset="us-ascii"
> 
> 
> On 28/05/2010, at 8:53 AM, Quets Jan wrote:
> 
> > 
> > Hi,
> > 
> > I am looking for a specific non-overlapping marked spatial model for use as a null model for monte carle simulations with use of the 'envelope' function in spatstat.
> > 
> > the specific marked spatial model should:
> > -----------------
> > *generate a spatial random pattern with a predetermined number of points (with conditions set below)
> > 
> > *each point should be assigned a mark randomly out of a predetermined set of marks
> > 
> > *these marks represent the radia of circular discs which should be drawn around these points (which act as centres)
> > 
> > *no discs should overlap
> > -----------------
> > 
> > Does anybody has knowledge of a such a built in model in spatstat or another R package?
> > 
> > For now, I have built this model by myself, but it turns out to have a very time-consuming running time, especially when used as a null model in a monte carlo simulation. Also I have multiple monte carlo simulations to perform.
> > 
> > It will be of great help,
> 
> The only way I can think of doing this is sequentially.  I.e. select a
> radius,
> then repetitively select a point to add, rejecting the selected point if
> its
> circle (with the chosen radius) intersects any of the existing circles. 
> If
> after ``giveup'' attempts the function has failed to find an acceptable
> point,
> it gives up (and throws an error).
> 
> I cobbled together some code to effect this; it took one minute of user
> time
> to do 100 replications of choosing 100 points with non-overlapping
> circles
> in the unit square, with the radii selected uniform-randomly from
> (1:5)/100
> and giveup=1000.
> 
> I believe that it would require a lot of work and great cleverness to get
> anything substantially faster.  Of course, I could be wrong --- I was
> once,
> back in 1968 when I thought I'd made a mistake and I hadn't. :-)
> 
> 	cheers,
> 
> 		Rolf Turner
> 
> P. S.  Let me know if you want my code.  I suspect it's not much
> different
> from what you have built yourself.
> 
> 		R.
> ######################################################################
> Attention: 
> This e-mail message is privileged and confidential. If you are not the 
> intended recipient please delete the message and notify the sender. 
> Any views or opinions presented are solely those of the author.
> 
> This e-mail has been scanned and cleared by MailMarshal 
> www.marshalsoftware.com
> ######################################################################
> 
>