CGAL users discussion list

[Manuel Holtgrewe <>]

Hi Manuel,

Thanks for your answer.

I have attached the now hopefully correct program for leveraging the
Delaunay Hierarchy in nearest neighbour queries.

Maybe it is of use to someone. Here are the juicy bits of the
program's output on my machine:

$>./test_dh_finger
Delaunay Hierarchy:  finger query vs. non-finger query
         n dt_no_finger  dt_finger  dh_no_finger  dh_finger  dh_speedup
         2     0.550073   0.494133      0.499732   0.492765    1.014139
         4     0.180180   0.143496      0.150785   0.145044    1.039580
         8     0.042447   0.040908      0.048284   0.040934    1.179556
        16     0.187192   0.181526      0.194100   0.180929    1.072796
        32     0.072436   0.058800      0.078396   0.058778    1.333770
        64     0.146741   0.123116      0.154736   0.123907    1.248807
       128     0.131286   0.088024      0.136889   0.088209    1.551872
       256     0.144457   0.086384      0.150825   0.086563    1.742375
       512     0.186457   0.084601      0.192442   0.084808    2.269152
      1024     0.215611   0.069493      0.116932   0.069964    1.671317
      2048     0.297175   0.074581      0.141820   0.074778    1.896554
      4096     0.383350   0.069184      0.169974   0.069191    2.456590
      8192     0.527038   0.068528      0.177454   0.068764    2.580625
     16384     0.708779   0.066241      0.150414   0.066194    2.272327
     32768     1.047828   0.072765      0.165167   0.072591    2.275306
     65536     1.481253   0.069943      0.178241   0.069794    2.553818
    131072     2.243405   0.070851      0.196017   0.070185    2.792864
    262144     3.585705   0.072495      0.222337   0.071803    3.096482
    524288     6.232107   0.071436      0.255025   0.070398    3.622623
   1048576    13.459370   0.073421      0.200260   0.072325    2.768890

-- Manuel



2009/4/22 Manuel Caroli 
<>:
> Hi Manuel,
>
> you are right. Unlike point location the nearest vertex query is not
> overloaded by the triangulation hierarchy. Followingly the one from DT is
> called.
>
> Best
>
> Manuel
>
>
> Manuel Holtgrewe wrote:
>>
>> Sylvain,
>>
>> thanks for your answer. However, please have another look at the data
>> (I cut out the lesse interesting columns so the table is not wrapped.
>>
>> Note that I am also performing a query without hints. In this case, I
>> would expect the delaunay hierarchy to be faster than the delaunay
>> triangulation.
>>
>> Could someone compile the source file (reattached in this email) and
>> verify my results?
>>
>> Somehow, I have the impression that the same code is called for the
>> delaunay triangulation and the delaunay hierarchy.
>>
>> Bests,
>> Manuel
>>
>>      n   dt_no_finger  dt_finger  dh_no_finger  dh_finger
>>      2       0.505304   0.477886      0.475679   0.475234
>>      4       0.103188   0.102858      0.102885   0.101524
>>      8       0.042936   0.041076      0.043392   0.041294
>>     16       0.056725   0.047944      0.056533   0.048035
>>     32       0.075375   0.059116      0.075654   0.059563
>>     64       0.088672   0.062105      0.088614   0.062050
>>    128       0.132514   0.086989      0.132462   0.087279
>>    256       0.140531   0.078194      0.140511   0.078217
>>    512       0.175971   0.064753      0.173778   0.064725
>>   1024       0.222064   0.069129      0.221879   0.069079
>>   2048       0.299477   0.067341      0.298769   0.067386
>>   4096       0.392608   0.066532      0.393548   0.066462
>>   8192       0.547986   0.069801      0.546512   0.069839
>>  16384       0.741440   0.066260      0.741307   0.066181
>>  32768       1.080815   0.067014      1.084949   0.066969
>>  65536       1.518390   0.066989      1.512893   0.067106
>>  131072       2.312096   0.070554      2.320022   0.071241
>>  262144       3.690626   0.072124      3.677720   0.071980
>>  524288       6.416665   0.072153      6.279038   0.071597
>> 1048576      13.649976   0.072951     13.965254   0.074540
>> 2097152      27.961286   0.075513     27.911974   0.075280
>> 4194304      48.720407   0.079028     49.280193   0.078284
>>
>> -- Manuel
>>
>>
>>
>> 2009/4/20 Damian Sheehy 
>> <>:
>>>
>>> Sylvain,
>>>
>>> Thank you for enlightening me!  :)
>>>
>>> Manuel,
>>>
>>> Your non-hierarchical triangulation (dt_build in your notation) calls the
>>> dt.insert(begin, end) interface. This interface performs preprocessing to
>>> sort the points along a Hilbert curve which improves the performance of
>>> insertion. I did not factor this in when I compared computation times for
>>> the Delaunay and the Delaunay+hierarchy construction. To perform an
>>> apple-to-apple comparison of the performance of these two algorithms you
>>> should use the dt/dh.insert(Point) interface.
>>>
>>> So in summary, the hierarchy is not being leveraged during construction
>>> because the sort ensures the resulting sequence of points is in close
>>> geometric proximity; the hierarchy is not being leveraged during
>>> nearest_vertex queries because you are already providing a good starting
>>> hint. Conclusion, the hierarchy is not doing anything for you so you
>>> don't
>>> need it.
>>>
>>>
>>> Best regards,
>>>
>>> Damian
>>>
>>> On Sun, Apr 19, 2009 at 8:10 AM, Sylvain Pion
>>> <>
>>> wrote:
>>>>
>>>> Hi Damian,
>>>>
>>>> Damian Sheehy a écrit :
>>>>>
>>>>> For a random set of points the Delaunay hierarchy should build a
>>>>> triangulation in much less time than the conventional Delaunay without
>>>>> a
>>>>> hierarchy. The numbers do not reflect that, so something is wrong. I
>>>>> will
>>>>> run your example tomorrow and see what I get. . .
>>>>
>>>> This is not true anymore in recent CGAL releases, more precisely
>>>> since the introduction of a spatial sorting preprocessing phase (BRIO).
>>>>
>>>> --
>>>> Sylvain Pion
>>>> INRIA Sophia-Antipolis
>>>> Geometrica Project-Team
>>>> CGAL, http://cgal.org/
>>>> --
>>>> You are currently subscribed to cgal-discuss.
>>>> To unsubscribe or access the archives, go to
>>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>>>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>

Attachment: test_dh_finger.cpp
Description: Binary data