CGAL users discussion list

[Manuel Holtgrewe <>]

Hi Damian,

Thank you for your answer.

I have written a little program with which I am trying to measure the
speedup that the fingers give me. The source code is attached, I
tested it with CGAL 3.4 on a machine with Intel Xeon processors
@2.3Ghz.

I get the following output:

Delaunay Hierarchy:  finger query vs. non-finger query
         n      build  no_finger     finger    speedup
         2   0.000012   0.424343   0.425491   0.997302
         4   0.000018   0.086763   0.086414   1.004036
         8   0.000015   0.100489   0.099627   1.008651
        16   0.000033   0.114695   0.105578   1.086352
        32   0.000066   0.128658   0.123606   1.040871
        64   0.000134   0.135320   0.116303   1.163512
       128   0.000270   0.178627   0.143877   1.241526
       256   0.000539   0.174100   0.122833   1.417371
       512   0.001070   0.168988   0.150091   1.125904
      1024   0.002091   0.173133   0.160160   1.080999
      2048   0.004395   0.185442   0.175380   1.057372
      4096   0.008549   0.207307   0.195271   1.061638
      8192   0.017413   0.216792   0.208223   1.041154
     16384   0.033093   0.246830   0.232705   1.060700
     32768   0.067720   0.198592   0.188638   1.052769
     65536   0.135914   0.207161   0.195284   1.060819
    131072   0.281401   0.243547   0.232596   1.047081
    262144   0.561701   0.254221   0.240915   1.055233
    524288   1.137475   0.238146   0.225836   1.054509
   1048576   2.287607   0.250391   0.238223   1.051078
   2097152   4.772575   0.252274   0.239942   1.051396
   4194304   9.628133   0.282821   0.270887   1.044055
   8388608  19.543273   0.305526   0.292194   1.045627

As you can see, I could only measure very small speedups. I would
expect them to be much bigger. Am I doing something wrong?

-- Manuel



2009/4/17 Damian Sheehy 
<>:
> Hi Manuel,
>
> Based on visual inspection, your code looks correct. You do not have
> to special case the first nearest_vertex search; just pass a default
> Face_handle in the first iteration of the loop and start the loop from
> zero.
>
> Regards,
>
> Damian
>
> On 4/17/09, Manuel Holtgrewe 
> <>
>  wrote:
>> Hi,
>>
>> I am trying to perform finger search with the delaunay hierarchy code
>> from CGAL. That is, I have a random point set which is added as the
>> points of a delaunay hierarchy / triangulation. Then, I have a list of
>> query points which lie along a line through this point set. I want to
>> query for the nearest neighbours of the points on the line.
>>
>> This sequence of queries should offer good locality, i.e. if I know
>> the nearest neighbour x of point i on the line, the nearest neighbour
>> y of point i+1 should be very close to x. Thus, I am trying to use the
>> second parameter to Delaunay_triangulation_2::nearest_vertex(const
>> Point& p, Face_handle f= Face_handle()) const.
>>
>> Will the following code do this, i.e. when calling x->face() (where x
>> is the nearest neighbour of the i-th query point i), will this return
>> a face adjacent to x and this helps to speed up the queries?
>>
>> Thanks,
>> Manuel
>>
>> // typedefs/aliases
>> struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
>>
>> typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
>> typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
>> typedef CGAL::Triangulation_face_base_2<K>                Fb;
>> typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;
>>
>> typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
>> typedef CGAL::Triangulation_hierarchy_2<Dt>
>> Triangulation_hierarchy;
>> typedef Triangulation_hierarchy::Vertex_circulator
>> Vertex_circulator_hierarchy;
>> typedef Triangulation_hierarchy::Point                    Point_hierarchy;
>> typedef Triangulation_hierarchy::Vertex                   Vertex_hierarchy;
>> typedef Triangulation_hierarchy::Vertex_handle
>> Vertex_hierarchy_handle;
>> typedef Triangulation_hierarchy::Face_handle
>> Face_hierarchy_handle;
>>
>> void foo(const std::vector<Point_hierarchy> &points, const
>> std::vector<Point_hierarchy> &queries) {
>>  Triangulation_hierarchy dh;
>>   dh.insert(points.begin(), points.end());
>>   Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
>>   Face_hierarchy_handle f = v->face();
>>   for (int j = 1, jend = queries.size(); j < jend; ++j) {
>>     v = dh.nearest_vertex(queries[j], f);
>>     f = v->face();
>>   }
>> }
>> --
>> 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