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

[Nicholas Lewin-Koh]

Ok My 2c is going to go up to a quarter. Having discussed this a little
more 
with a colleague, we realized that a sequential approach may not work so
well,
because in a finite region so many configurations would be inadmissible
and and
you would have to reject the whole thing, unless the density of disks 
is sparse. So this really is a yucky problem.

Nicholas 

On Fri, 28 May 2010 08:51 -0700, "Nicholas Lewin-Koh"
<nikko at hailmail.net> wrote:
> 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
> > ######################################################################
> > 
> > 
> 
>