libs/polygon/doc/voronoi_main.htm

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html><head>
   3
   4
   5
   6
   7   <meta http-equiv="Content-Language" content="en-us">
   8   <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Main</title>
   9
  10   <meta http-equiv="content-type" content="text/html; charset=utf-8">
  11   <meta http-equiv="content-type" content="text/html; charset=utf-8">
  12   <meta http-equiv="content-type" content="text/html; charset=utf-8">
  13   <meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
  14 <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
  15   <tbody>
  16     <tr>
  17       <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  18       <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
  19       <div style="margin: 5px;">
  20       <h3 class="navbar">Contents</h3>
  21       <ul>
  22         <li><a href="index.htm">Boost.Polygon Main Page</a></li>
  23         <li><a href="gtl_design_overview.htm">Design Overview</a></li>
  24         <li><a href="gtl_isotropy.htm">Isotropy</a></li>
  25         <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
  26         <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
  27         <li><a href="gtl_point_concept.htm">Point Concept</a></li>
  28         <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
  29         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
  30         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
  31         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
  32 With Holes Concept</a></li>
  33         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
  34         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
  35 With Holes Concept</a></li>
  36         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
  37         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
  38 Holes Concept</a></li>
  39         <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
  40 Concept</a></li>
  41         <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  42 Concept</a></li>
  43         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  44         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  45 Extraction 90</a></li>
  46         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  47 Extraction 45</a></li>
  48         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  49 Extraction</a></li>
  50         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  51         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  52         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  53         <li>Voronoi Main Page </li>
  54         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li>
  55         <li><a href="voronoi_builder.htm">Voronoi Builder</a> </li>
  56         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  57       </ul>
  58       <h3 class="navbar">Other Resources</h3>
  59       <ul>
  60         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  61         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  62 Presentation</a></li>
  63         <li><a href="analysis.htm">Performance Analysis</a></li>
  64         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  65         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  66         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  67         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  68 Tutorial</a></li>
  69       </ul>
  70       </div>
  71       <h3 class="navbar">Polygon Sponsor</h3>
  72       <div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
  73       </td>
  74       <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
  75       <h1>THE BOOST.POLYGON VORONOI LIBRARY </h1>
  76       <img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
  77 The Voronoi extension of the Boost.Polygon library provides
  78 functionality to construct a <a href="voronoi_diagram.htm">Voronoi
  79 diagram</a>
  80 of a set of points and linear segments in 2D space with the following
  81 set of
  82 limitations:<br>
  83       <ul>
  84         <li>coordinates of the input points and endpoints of the
  85 input segments
  86 should be of the integer type;</li>
  87         <li>input segments should not overlap
  88 except their endpoints.</li>
  89       </ul>
  90 While the first restriction is permanent (it
  91 allows to give the exact warranties about the output precision and
  92 algorithm execution flow),
  93 the second one may be resolved using the Boost.Polygon <a href="gtl_segment_concept.htm">segment utils</a>.
  94 The strong sides of the
  95 library and main benefits comparing to the other implementations are
  96 discussed in the following paragraphs.<br>
  97 <h2>Fully Functional with Segments</h2>
  98 There are just a few implementations of the Voronoi diagram
  99 construction
 100 algorithm that can
 101 handle input data sets that contain linear segment, even considering
 102 the commercial
 103 libraries.
 104 Support of the
 105 segments allows to discretize any input geometry (sampled
 106 floating-point coordinates can be scaled and snapped to the integer
 107 grid): circle, ellipse,
 108 parabola. This functionality allows to compute
 109 the medial axis transform of the arbitrary set of input geometries,
 110 with direct applications in the computer vision
 111 projects.
 112       <h2>Robustness and Efficiency</h2>
 113 Robustness issues can be divided onto the two main categories: memory
 114 management
 115 issues and numeric stability issues. The implementation avoids the
 116 first type of the issues using pure STL data structures, thus there is
 117 no
 118 presence of the new operator in the code. The second category of
 119 the problems is
 120 resolved using the multiprecision geometric
 121 predicates.
 122 Even for the commercial libraries, usage of such predicates
 123 results in a vast performance slowdown. The Voronoi implementation
 124 overcomes this by avoiding the multiprecision
 125 computations in the 95% of the cases and
 126 uses the efficient, floating-point based predicates. Such preciates
 127 don't
 128 produce the correct result always, however the library embeds the
 129 relative
 130 error arithmetic apparatus to identify such situations and switch
 131 to the
 132 higher precision predicates when appropriate. As the result, the
 133 implementation has a solid performance comparing to the other known
 134 libraries (more details in the <a href="voronoi_benchmark.htm">benchmarks</a>).<br>
 135       <h2>Precision of the Output Structures </h2>
 136 The Voronoi implementation guaranties, that the relative error of the
 137 coordinates of the output
 138 geometries is at most 64 machine epsilons (6
 139 bits of mantissa, for the IEEE-754 floating-point type), while on
 140 average it's slightly lower. This means, that the precision of the
 141 output
 142 geometries can be increased simply by using a floating-point type with
 143 the larger mantissa. The practical point of this statements is
 144 explained in the following table:<br>
 145       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 146         <tbody>
 147           <tr>
 148             <td style="vertical-align: top;">Output Coordinate Type </td>
 149             <td style="vertical-align: top;">Output Coordinate Value </td>
 150             <td style="vertical-align: top;">Max Absolute Error </td>
 151             <td style="vertical-align: top;">Precise Value Range </td>
 152           </tr>
 153           <tr>
 154             <td style="vertical-align: top;">double (53 bit mantissa) </td>
 155             <td style="vertical-align: top;">1 </td>
 156             <td style="vertical-align: top;">2<sup>-53</sup> * 2<sup>6</sup>
 157 = 2<sup>-47</sup></td>
 158             <td style="vertical-align: top;">1 ± 2<sup>-47</sup></td>
 159           </tr>
 160           <tr>
 161             <td style="vertical-align: top;">double (53 bit mantissa) </td>
 162             <td style="vertical-align: top;">2<sup>31</sup> </td>
 163             <td style="vertical-align: top;">2<sup>-53</sup> * 2<sup>31</sup>
 164 * 2<sup>6</sup> = 2<sup>-16</sup></td>
 165             <td style="vertical-align: top;">2<sup>31</sup> ± 2<sup>-16</sup></td>
 166           </tr>
 167           <tr>
 168             <td style="vertical-align: top;">long double (64 bit
 169 mantissa)</td>
 170             <td style="vertical-align: top;">1 </td>
 171             <td style="vertical-align: top;">2<sup>-64</sup> * 2<sup>6</sup>
 172 = 2<sup>-58</sup></td>
 173             <td style="vertical-align: top;">1 ± 2<sup>-58</sup></td>
 174           </tr>
 175           <tr>
 176             <td style="vertical-align: top;">long double (64 bit
 177 mantissa) </td>
 178             <td style="vertical-align: top;">2<sup>31</sup></td>
 179             <td style="vertical-align: top;">2<sup>-64</sup> * 2<sup>31</sup>
 180 * 2<sup>6</sup> = 2<sup>-27</sup></td>
 181             <td style="vertical-align: top;">2<sup>31</sup> ± 2<sup>-27</sup></td>
 182           </tr>
 183         </tbody>
 184       </table>
 185 Detailed description of the absolute and relative errors evaluation can
 186 be found in the article: <a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">"What
 187 Every Computer Scientist Should Know About Floating-Point Arithmetic"</a><a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html"></a>.<br>
 188       <br>
 189 During the finalization step the implementation unites the Voronoi
 190 vertices
 191 whose both
 192 coordinates are situated within the relative error range equal to 128
 193 machine epsilons and removes any Voronoi edges between those. This is
 194 the only case, that might cause differences between the algorithm
 195 output
 196 topology and theoretically precise one, and practically means the
 197 following: for the Voronoi diagram of a set of solid bodies inside the
 198 Solar System (radius 2<sup>42</sup> metres) and the long double (64 bit
 199 mantissa) output coordinate type the maximum absolute error within the
 200 Solar System rectangle will be equal to 2<sup>-64</sup> * 2<sup>42</sup>
 201 * 2<sup>6</sup> = 2<sup>-18</sup> metres; as the result, vertices with
 202 both coordinates that are within 2<sup>-18</sup> metres (8
 203 micrometres or the size of a bacteria) will be considered
 204 equal and united.<br>
 205       <h2>Simple Interface </h2>
 206 The <a href="../../../boost/polygon/voronoi.hpp">boost/polygon/</a><a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a>
 207 library header defines the following static functions to integrate the
 208 Voronoi library
 209 functionality with the Boost.Polygon interfaces:<br>
 210       <br>
 211       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 212         <tbody>
 213           <tr>
 214             <td style="font-family: Courier New,Courier,monospace;">template
 215 &lt;typename Point, typename VB&gt;<br>
 216 size_t <span style="font-weight: bold;">insert</span>(const Point
 217 &amp;point, VB *vb) </td>
 218             <td>Inserts a point into the Voronoi builder data structure.<br>
 219 Point type should model the point concept.<br>
 220 Returns index of the inserted site. </td>
 221           </tr>
 222           <tr>
 223             <td style="font-family: Courier New,Courier,monospace;">template
 224 &lt;typename PointIterator, typename VB&gt;<br>
 225 void <span style="font-weight: bold;">insert</span>(PointIterator
 226 first, <br>
 227 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 228 PointIterator last,<br>
 229 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; VB
 230 *vb) </td>
 231             <td>Inserts an iterator range of points into the Voronoi
 232 builder data structure.<br>
 233 Corresponding point type should model the point concept. </td>
 234           </tr>
 235           <tr>
 236             <td style="font-family: Courier New,Courier,monospace;">template
 237 &lt;typename Segment, typename VB&gt;<br>
 238 size_t <span style="font-weight: bold;">insert</span>(const Segment
 239 &amp;segment, VB *vb) </td>
 240             <td>Inserts a segment into the Voronoi builder data
 241 structure.<br>
 242 Segment type should model the segment concept.<br>
 243 Returns index of the inserted site. </td>
 244           </tr>
 245           <tr>
 246             <td style="font-family: Courier New,Courier,monospace;">template
 247 &lt;typename SegmentIterator, typename VB&gt;<br>
 248 void <span style="font-weight: bold;">insert</span>(SegmentIterator
 249 first,<br>
 250 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 251 SegmentIterator last,<br>
 252 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; VB
 253 *vb) </td>
 254             <td>Inserts an iterator range of segments into the Voronoi
 255 builder data structure.<br>
 256 Corresponding segment type should model the segment concept. </td>
 257           </tr>
 258           <tr>
 259             <td style="font-family: Courier New,Courier,monospace;">template
 260 &lt;typename PointIterator, typename VD&gt;<br>
 261 void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator
 262 first,<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 263 PointIterator last,<br>
 264 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 265 VD *vd) </td>
 266             <td>Constructs the Voronoi diagram of a set of points.<br>
 267 Corresponding point type should model the point concept.<br>
 268 Complexity: O(N * log N), memory usage: O(N), where N is the total number of input points.<br>
 269  </td>
 270           </tr>
 271           <tr>
 272             <td style="font-family: Courier New,Courier,monospace;">template
 273 &lt;typename SegmentIterator, typename VD&gt;<br>
 274 void <span style="font-weight: bold;">construct_voronoi</span>(SegmentIterator
 275 first,<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 276 SegmentIterator last,<br>
 277 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 278 VD *vd) </td>
 279             <td>Constructs the Voronoi diagram of a set of segments.<br>
 280 Corresponding segment type should model the segment concept.<br>
 281 Complexity: O(N * log N), memory usage: O(N), where N is the total number of input segments.<br>
 282  </td>
 283           </tr>
 284           <tr>
 285             <td style="font-family: Courier New,Courier,monospace;">template
 286 &lt;typename PointIterator,<br>
 287 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename
 288 SegmentIterator,<br>
 289 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename VD&gt;<br>
 290 void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator
 291 p_first,<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 292 PointIterator p_last,<br>
 293 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 294 SegmentIterator s_first,<br>
 295 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 296 SegmentIterator s_last,<br>
 297 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 298 VD *vd) </td>
 299             <td>Constructs the Voronoi
 300 diagram of a set of points and segments.<br>
 301 Corresponding point type should model the point concept.<br>
 302 Corresponding segment type should model the segment concept.<br>
 303 Complexity: O(N* log N), memory usage: O(N), where N is the total number of input points and segments.<br>
 304 </td>
 305           </tr>
 306         </tbody>
 307       </table>
 308       <br>
 309 The
 310 following two lines of code construct the Voronoi diagram of a set of
 311 points (as
 312 long as the corresponding input geometry type satisfies the
 313 Boost.Polygon <a href="gtl_design_overview.htm">concept model</a>):<br>
 314       <br>
 315       <span style="font-family: Courier New,Courier,monospace;">voronoi_diagram&lt;double&gt;
 316 vd;</span><br style="font-family: Courier New,Courier,monospace;">
 317       <span style="font-family: Courier New,Courier,monospace;">construct_voronoi(points.begin(),
 318 points.end(), &amp;vd);</span><br>
 319       <br>
 320 The library provides the clear interfaces to associate the user data
 321 with the
 322 output geometries and efficiently traverse
 323 the
 324 Voronoi graph.
 325 More details on those topics are covered in the <a href="voronoi_basic_tutorial.htm">basic Voronoi tutorial</a>. Advanced
 326 usage of the library with the configuration of the coordinate
 327 types is explained in the <a href="voronoi_advanced_tutorial.htm">advanced
 328 Voronoi tutorial</a>.
 329 The library allows users to implement their own Voronoi diagram /
 330 Delaunay triangulation construction routines based on the <a href="voronoi_builder.htm">Voronoi builder API</a>.<br>
 331       <h2>No Third Party Dependencies </h2>
 332 The Voronoi extension of the Boost.Polygon library doesn't depend on
 333 any 3rd party code
 334 and contains single dependency on the Boost libraries:
 335 boost/cstdint.hpp.
 336 All the required multiprecision types and related functionality are
 337 encapsulated as
 338 part of the implementation. The library is fast to compile (3 public
 339 and 4 private heades), has strong cohesion between its components and
 340 is clearly modularized from the rest of the Boost.Polygon library, with
 341 the optional integration through the <a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a> header.<br>
 342       <h2>Extensible for the User Provided Coordinate Types</h2>
 343 The implementation is coordinate type agnostic. As long
 344 as the user provided types satisfy the set of the requirements of the <a href="voronoi_builder.htm">Voronoi builder</a> coordinate type traits,
 345 no additional
 346 changes
 347 are needed
 348 neither to the algorithm, nor to the implementation of the predicates.
 349 For example, it's
 350 possible to
 351 construct the Voronoi diagram with the 256-bit integer input coordinate
 352 type
 353 and
 354 512-bit output floating-point type without making any changes to the
 355 library.<br>
 356       <h2>Future Development </h2>
 357 Below one may find the list of the main directions for the future
 358 development of the library.<br>
 359 The high-priority tasks that already have the approximate
 360 implementation plan
 361 are the following (some of those may be proposed as future GSoC
 362 projects):<br>
 363       <ul>
 364         <li>Implement the Delaunay triangulation data structure.<br>
 365 Note: only data structure needs to be implemented that properly
 366 processes events provided by the Voronoi builder.</li>
 367         <li>Implement the medial axis transform data structure.<br>
 368 Note: in general case the Voronoi diagram has completely the same
 369 geometry
 370 as the medial axis (they are 100% equal), however for many applications
 371 user is not interested in the Voronoi edges inside the hole regions.
 372 The main point
 373 of this data structure is to automatically filter the Voronoi edges
 374 that
 375 belong to those areas.</li>
 376         <li>The Voronoi
 377 diagram data structure can be used to find the K nearest neighbors of
 378 the N
 379 sites in O(N*K*log(K) + N*log(N)) time. The return value would be a
 380 list of the k nearest neighbors for each site. </li>
 381         <li>Use the r-tree data structure built on top of the
 382 bounding rectangles around the Voronoi cells to answer the nearest
 383 neighbor queries in log(N) time, where N is the number of the Voronoi
 384 cells.<br>
 385 Note: there should be r-tree data structure available soon as part of
 386 the Boost libraries.</li>
 387         <li>Expose O(N) interface to retrieve the convex hull of a set
 388 of
 389 points and segments from the Voronoi builder, once the Voronoi diagram
 390 is
 391 constructed.</li>
 392         <li>Provide serialization utilities for the Voronoi diagram
 393 data structure. </li>
 394       </ul>
 395 High-priority tasks to be considered:<br>
 396       <ul>
 397         <li>Drop the restriction on the non-intersecting input
 398 geometries.</li>
 399         <li>Integrate the Voronoi diagram data structure with the
 400 BGL (Boost
 401 Graph Library).</li>
 402         <li>Support the other types of distance metrics.</li>
 403         <li>Construction of the constrained Delaunay triangulation.</li>
 404         <li>Support of the circular input geometries.</li>
 405       </ul>
 406 Based on the community suggestions priorities may be changed.<br>
 407       <h2>Theoretical Research </h2>
 408 The Voronoi library
 409 was developed as part of the Google Summer of Code 2010. The
 410 library was actively maintained for the last three years and involved
 411 the
 412 strong mathematical research in the field of algorithms, data
 413 structures,
 414 relative error arithmetic and numerical robustness. Nowadays one can
 415 often read a scientific paper, that contains non-practical
 416 theoretical
 417 results or implementation with
 418 benchmarks nobody else can reproduce. The opposite story is with
 419 the Voronoi library, that contains complete
 420 implementation of
 421 the Voronoi diagram construction algorithm and
 422 benchmarks one may run on
 423 his/her PC. Upon the community request, more documentation on the
 424 theoretical aspects of the implementation will be published.
 425 The
 426 authors would like to acknowledge the Steven Fortune's article <span style="font-family: Arial,Helvetica,sans-serif;"><span style="font-weight: bold;"></span></span>"<a href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm
 427 for Voronoi diagrams</a>", that covers fundamental ideas of the
 428 current implementation. </td>
 429     </tr>
 430     <tr>
 431       <td style="background-color: rgb(238, 238, 238);" nowrap="1">&nbsp;</td>
 432       <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
 433       <table class="docinfo" id="table2" frame="void" rules="none">
 434         <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
 435           <tr>
 436             <th class="docinfo-name">Copyright:</th>
 437             <td>Copyright © Andrii Sydorchuk 2010-2013.</td>
 438           </tr>
 439           <tr class="field">
 440             <th class="docinfo-name">License:</th>
 441             <td class="field-body">Distributed under the Boost Software
 442 License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
 443 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 444           </tr>
 445         </tbody>
 446       </table>
 447       </td>
 448     </tr>
 449   </tbody>
 450 </table>
 451
 452 </body></html>