## Optical generation of Voronoi Diagram

Optics Express, Vol. 16, Issue 7, pp. 4819-4823 (2008)

http://dx.doi.org/10.1364/OE.16.004819

Acrobat PDF (1453 KB)

### Abstract

We present results of experiments of diffraction by an amplitude screen, made of randomly distributed circular holes. By careful selection of the experimental parameters we obtain an intensity pattern strongly connected to the Voronoi diagram (VD) generated by the centers of the apertures. With the help of simulations we give a description of the observed phenomenon and elucidate the optimal parameters for its observation. Finally, we also suggest how it can be used for a fast, all-optical generation of VDs.

© 2008 Optical Society of America

## 1. Introduction

3. G. Schliecker, “Structure and dynamics of cellular systems,” Adv. Phys. **51**, 1319–1378 (2002). [CrossRef]

4. H. X. Zhu, S. M. Thorpe, and A. H. Windle, “The geometrical properties of irregular two-dimensional Voronoi tessellations,” Philos. Mag. A **81**, 2765 (2001). [CrossRef]

6. D. Tolmachiev and A. Adamatzky, “Chemical processor for computation of Voronoi diagram,” Adv. Mater. Opt. Electron. **6**, 191 (1996). [CrossRef]

7. M. Doi, Y. Suzuki, T. Koyama, and F. Katsuki, “Pattern evolution of crystalline Ge aggregates during annealing of an Al/Ge bilayer film deposited on a SiO_{2} substrate,” Philos. Mag. Lett. **78**, 241 (1998). [CrossRef]

8. A. L. Zanin, A. W. Liehr, A. S. Moskalenko, and H.-G. Purwins, “Voronoi diagrams in barrier gas discharge,” Appl. Phys. Lett. **81**, 3338 (2002). [CrossRef]

## 2. Experimental procedure

*z*>0 diffraction fringes are expected to appear inside the image of each hole. In practice, the fringes visibility is limited by both the finite bandwidth Δ

*λ*of the radiation employed and the finite resolution of the sensor. These limitations impose lower bounds on the observation distance

*z*allowing the diffractive effects to be appreciable, respectively:

*z*>

*R*

^{2}Δ

*λ*/

*λ*

^{2}

_{0}≈0.07

*cm*and

*z*>4

*R*

^{2}/

*nλ*

_{0}(

*λ*

_{0}being the central wavelength of the light and

*n*the width (in pixels) of the hole image recorded by the sensor). In our experimental condition (

*n*≈20 pixels) the second condition is the most stringent and reads:

*z*>0.7

*cm*. If

*z*is further increased, also the interference between the light scattered from different apertures becomes visible.

*z*=1.7

*cm*) is shown in Fig. 2(a). The same image is shown in Fig 2(b) with a

*γ*=0.25 correction, while in Fig. 2(c) we have superimposed to the

*γ*-corrected image the VD calculated from the centers of the holes (

*i.e.*having the center of the holes as generating set). Note that the chosen

*z*value corresponds to a Fresnel number

*F*≡

*R*

^{2}/

*λz*≈2, yielding the dark Poisson’s spots lying at the centers of the images of holes. Therefore, in the conditions outlined above, the optical processor described in this paper allows to visualize both the VD and the position of the generator points of the diagram.

*z*is further increased, the intensity distribution is no longer determined just by the interference between the light emerging from geometrical neighbors apertures: each point on the sensor receives light from a region containing a large number of holes. If the size of the contributing region is smaller than the size of a coherently illuminated region, then a speckle pattern is formed. The latter is characterized by the recently discovered [9

9. M. Giglio, M. Carpineti, and A. Vailati, “Space intensity correlations in the near field of the scattered light: A direct measurement of the density correlation function *g*(*r*),” Phys. Rev Lett. **85**, 1416 (2000). [CrossRef] [PubMed]

*z*[10].

## 3. Discussion

*R*, whose centers lie at a distance

*d*>2

*R*(Fig. 3(a)).

*λ*impinges on the screen, the light diffracted by each hole is concentrated in a forward scattering lobe of increasing cross-section. Following the simple argument outlined in Reference 11 one can estimate the linear size of each diffraction spot at a distance

*z*<

*R*

^{2}/

*λ*from the screen as

*z*

^{*}from the screen at which the two lobes start to overlap is thus

*z*

^{*}≈(

*d*-2

*R*)

^{2}/4

*λ*. The interference pattern visible in the overlap region consists, as a first approximation, of sinusoidal fringes of wavelength Λ≈

*λz*/

*d*, parallel to the median of the centers. So, if the intensity distribution of the scattered light is recorded at a distance slightly larger than

*z*

^{*}such that the overlap region contains approximately one fringe, one expects to see two bright, nearly circularly symmetric spots separated by two parallel dark stripes at a distance Λ from each other. The dark stripes surround the maximum of the interference fringes, which appears as a bright line acting as an axis of symmetry for the hole centers. This situation is depiced in Fig. 3(b). Here the intensity distribution

*I*on the plane

*z*=

*R*

^{2}/

*λF*(

*F*=3) has been calculated numerically by convolving the

*N*×

*N*(

*N*=1024) transmittancy matrix

*T*, whose 512×512 central part is shown in Fig. 3(a), with a discretized Fresnel propagation kernel. This operation is actually done in the frequency domain:

*I*=|ℑ

^{-1}(

*H*ℑ(

*T*))|

^{2}, where ℑ is the 2-dimensional discrete Fourier transform and

*d*, the above reasoning can be iterated for every pair of neighboring holes. The resulting intensity distribution will then contain all the medians of pairs of neighboring holes. These medians coincide with the edges separating the Voronoi domains associated with the centers of the pinholes (Fig. 3(c)).

*z*corresponding to a good visibility of the interference fringes depends both on the radius and the mutual distance between the holes. The uniform emergence of the whole Voronoi-like pattern is then guaranteed whenever the spacing between the centers of contiguous holes is approximately constant through the sample. This condition is automatically fulfilled, for example, by the important class of random close-packed (high surface fraction) monodisperse discs, which appears thus as an ideal candidate for the proposed technique [5].

*A*≫

*d*

^{2}, where

*A*is the typical surface of the coherence areas illuminating the screen. On the contrary, a loose temporal coherence of the source is not a problem, instead it can be even beneficial as it decreases the visibility of the unwanted diffraction fringes, whose wavelength is smaller then the width Λ of the interference stripes. This is apparent from Fig. 2, which was obtained by using a source with a limited temporal coherence (spectral bandwidth, FWHM, Δ

*λ*=13.1

*nm*).

^{3}×10

^{3}pixels and a typical pixel pitch (the center-to-center spacing between adjacent pixels) of 15

*µm*. Each pixel in a EASLM can be addressed independently to impose an amplitude (or phase, or both amplitude and phase) modulation on the light impinging on it. A group of pixels arranged into a circle can reproduce a circular aperture and many of such circular groups of pixels can be addressed onto a single amplitude EASLM, so that it mimics the perforated metallic screen used in this work. A EASLM has the great advantage that the position of the apertures can be changed at will, even in real time, thus providing a fast optical processing of the VD which can be immediately visualized onto the sensor.

## 4. Conclusion

*z*

^{*}exists for the formation of an interference pattern akin to the VD of the disc centers. This phenomenon can be exploited for a fast, fully reproducible, all-optical generation of the VD associated to a given distribution of generator points.

## References and Links

1. | G. Voronoi and J. Reine Angew, “Nouvelles applications des parametres continus à la theorie des formes quadratiques,” Math. |

2. | A. Okabe, B. Boots, and K. Sugihara, |

3. | G. Schliecker, “Structure and dynamics of cellular systems,” Adv. Phys. |

4. | H. X. Zhu, S. M. Thorpe, and A. H. Windle, “The geometrical properties of irregular two-dimensional Voronoi tessellations,” Philos. Mag. A |

5. | J. Lemaítre, A. Gervois, J. P. Troadec, N. Rivier, M. Ammi, L. Oger, and D. Bideau, “Arrangement of cells in Voronoi tesselations of monosize packing of discs,” Philos. Mag. B |

6. | D. Tolmachiev and A. Adamatzky, “Chemical processor for computation of Voronoi diagram,” Adv. Mater. Opt. Electron. |

7. | M. Doi, Y. Suzuki, T. Koyama, and F. Katsuki, “Pattern evolution of crystalline Ge aggregates during annealing of an Al/Ge bilayer film deposited on a SiO |

8. | A. L. Zanin, A. W. Liehr, A. S. Moskalenko, and H.-G. Purwins, “Voronoi diagrams in barrier gas discharge,” Appl. Phys. Lett. |

9. | M. Giglio, M. Carpineti, and A. Vailati, “Space intensity correlations in the near field of the scattered light: A direct measurement of the density correlation function |

10. | J. W. Goodman, |

11. | J. W. Goodman, |

12. | B. Jähne, |

13. | T. Bräunl, |

**OCIS Codes**

(070.0070) Fourier optics and signal processing : Fourier optics and signal processing

(200.4740) Optics in computing : Optical processing

(200.4960) Optics in computing : Parallel processing

**ToC Category:**

Fourier optics and signal processing

**History**

Original Manuscript: October 11, 2007

Revised Manuscript: November 22, 2007

Manuscript Accepted: November 30, 2007

Published: March 25, 2008

**Citation**

F. Giavazzi, R. Cerbino, S. Mazzoni, M. Giglio, and A. Vailati, "Optical generation of Voronoi diagram," Opt. Express **16**, 4819-4823 (2008)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-16-7-4819

Sort: Year | Journal | Reset

### References

- G. Voronoi and J. Reine Angew, "Nouvelles applications des parametres continus à la theorie des formes quadratiques," Math. 134, 198 (1908).
- A. Okabe, B. Boots, and K. Sugihara, Spatial Tesselations: Concept and Applications of Voronoi Diagrams (Wiley, Chichester, 1992).
- G. Schliecker, "Structure and dynamics of cellular systems," Adv. Phys. 51,1319-1378 (2002). [CrossRef]
- H. X. Zhu, S. M. Thorpe, and A. H. Windle, "The geometrical properties of irregular two-dimensional Voronoi tessellations," Philos. Mag. A 81, 2765 (2001). [CrossRef]
- J. Lemaítre, A. Gervois, J. P. Troadec, N. Rivier, M. Ammi, L. Oger, and D. Bideau, "Arrangement of cells in Voronoi tesselations of monosize packing of discs," Philos. Mag. B 81, 347 (1993).
- D. Tolmachiev and A. Adamatzky, "Chemical processor for computation of Voronoi diagram," Adv. Mater. Opt. Electron. 6, 191 (1996). [CrossRef]
- M. Doi, Y. Suzuki, T. Koyama, and F. Katsuki, "Pattern evolution of crystalline Ge aggregates during annealing of an Al/Ge bilayer film deposited on a SiO2 substrate," Philos. Mag. Lett. 78, 241 (1998). [CrossRef]
- A. L. Zanin, A. W. Liehr, A. S. Moskalenko, and H.-G. Purwins, "Voronoi diagrams in barrier gas discharge," Appl. Phys. Lett. 81, 3338 (2002). [CrossRef]
- M. Giglio, M. Carpineti, and A. Vailati, "Space intensity correlations in the near field of the scattered light: A direct measurement of the density correlation function g(r)," Phys. Rev Lett. 85, 1416 (2000). [CrossRef] [PubMed]
- J. W. Goodman, Speckle Phenomena in Optics (Greenwood Village, CO, 2007).
- J. W. Goodman, Introduction to Fourier Optics (McGraw-Hill), Chap. 4.
- B. Jähne, Digital Image Processing (Springer, 1995), Chap. 12.
- T. Bräunl, Parallel Image Processing (Springer, 2001), Chap. 5.

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.