File:Construction voronoi shamos.svg

From Wikimedia Commons, the free media repository
Jump to navigation Jump to search

Original file (SVG file, nominally 943 × 1,064 pixels, file size: 69 KB)

Captions

Captions

Add a one-line explanation of what this file represents

Summary

[edit]
Description
Français : Algorithme de Shamos pour la construction du diagramme de Voronoï (diviser pour régner).
  1. L'ensemble S est partitionné en deux sous-ensembles G (gauche, bleu) et D (droite, vert), pour lesquels on connaît le diagramme de Voronoï, resp. V(G) et V(D).
  2. On raccorde les enveloppes convexes C(G) et C(D), et on trace les médiatrices des segments de raccordement.
  3. On construit la ligne de soudure P.
  4. Les deux diagrammes sont raccordés.
English: Shamos algorithm to build the Voronoi diagram (divide-and-conquer).
  • The S set is divided int two subsets, G (left, blue) and D (right, green). Their respective Voronoi diagram is known: V(G) and V(D).
  • The convex hulls C(G) and C(D) are merged. We draw the bissectors of the lines linking the hulls.
  • The seam line P is built.
  • The diagrams are merged.
    		•
    Date
    Source Own work. Data set from File:Smallest circle problem.svg. Algorithm from Shamos, M. I. and Hoey, D., Closest-point problems, in Proceeding of 16th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, IEEE Computer Society Press, 1975
    Author Cdang
     
    This W3C-unspecified vector image was created with Inkscape .

    Licensing

    [edit]
    I, the copyright holder of this work, hereby publish it under the following license:
    w:en:Creative Commons
    attribution share alike
    This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.
    You are free:
    • to share – to copy, distribute and transmit the work
    • to remix – to adapt the work
    Under the following conditions:
    • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
    • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

    File history

    Click on a date/time to view the file as it appeared at that time.

    Date/TimeThumbnailDimensionsUserComment
    current15:03, 9 January 2013Thumbnail for version as of 15:03, 9 January 2013943 × 1,064 (69 KB)Cdang (talk | contribs){{Information |Description ={{en|1=one dashed line longer.}} |Source ={{own}} |Author =Cdang |Date = |Permission = |other_versions = }}
    14:45, 9 January 2013Thumbnail for version as of 14:45, 9 January 2013943 × 1,064 (69 KB)Cdang (talk | contribs)User created page with UploadWizard

    You cannot overwrite this file.

    There are no pages that use this file.

    File usage on other wikis

    The following other wikis use this file:

    Metadata

    This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.

    Retrieved from "https://commons.wikimedia.org/w/index.php?title=File:Construction_voronoi_shamos.svg&oldid=867777915"