7.7.2 Voronoi Diagrams, Delaunay Triangulation, 2-D Meshes

Voronoi, G.,
Nouvelles Applications des Parametres Continus a la Theorie des Formse Quadratiques. Duesieme Memoire: Recherches sur les Paralleloderes Primitifs,
J. Reine Angew. Math.(134), 1908, pp. 198-287. BibRef 0800

Gold, C.[Chris],
The Voronoi Web Site,
Online Book2004. 0410
WWW Version. The site devoted to the Voronoi Diagram, discussion, tutorials, everything you ever wanted to know. BibRef

Hjelle, Ř.[Řyvind], Morten, D.[Dćhlen],
Triangulations and Applications,
Springer2006, ISBN: 978-3-540-33260-2.
WWW Version. Theory behind the Delaunay triangulation. Theory necessary to construct and manipulate triangulations. BibRef 0600

Aurenhammer, F.[Franz],
Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure,
Surveys(23), No. 3, September 1991, pp. 345-405. Survey, Voronoi. BibRef 9109

Sibson, R.,
A vector identity for the Dirichlet tessellation,
CambridgePhil(87), 1980, pp. 151-155. BibRef 8000

Avis, D., and Bhattacharya, B.K.,
Algorithms for Computing D-Dimensional Voronoi Diagrams and Their Duals,
ACR(1), 1983, pp. 159-180. BibRef 8300

Ahuja, N.,
Dot Pattern Processing Using Voronoi Neighborhoods,
PAMI(4), No. 3, May 1982, pp. 336-343. BibRef 8205
Earlier:
Dot Pattern Processing Using Voronoi Polygons as Neighborhoods,
ICPR80(1122-1127). BibRef

Fairfield, J.,
Segmenting Dot Patterns by Voronoi Diagram Concavity,
PAMI(5), No. 1, January 1983, pp. 104-110. BibRef 8301

Fairfield, J.,
Segmenting Blobs into Subregions,
SMC(13), No. 3, 1983, pp. 363-384. BibRef 8300

Lee, D.T.,
On K-Nearest Neighbor Voronoi Diagrams in the Plane,
TC(31), 1982, pp. 478-487. BibRef 8200

Gowda, I.G., Kirkpatrick, D.G., Lee, D.T., Naamad, A.,
Dynamic Voronoi Diagrams,
IT(29), 1983, 724-731. BibRef 8300

Ahuja, N., An, B., Schachter, B.,
Image Representation Using Voronoi Tessellation,
CVGIP(29), No. 3, March 1985, pp. 286-295. BibRef 8503

An, B., Ahuja, N.,
Representation of Images Using Voronoi Tessellation,
CVPR83(188-189). BibRef 8300

Guibas, L.J., Stolfi, J.,
Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams,
TOG(4), 1985, pp. 74-123. BibRef 8500

Franklin, W.R., Akman, V., Verrilli, C.,
Voronoi Diagrams with Barriers and on Polyhedra for Minimal Path Planning,
VC(1), 1985, pp. 133-150. BibRef 8500

Lee, D.T.,
Relative neighborhood graphs in the Li-metric,
PR(18), No. 5, 1985, pp. 327-332.
WWW Version. 0309Construct the relative neighborhood graph based on the Delaunay triangulation. BibRef

Su, T.H.[Tung-Hsin], Chang, R.C.[Ruei-Chuan],
Computing the constrained relative neighborhood graphs and constrained gabriel graphs in Euclidean plane,
PR(24), No. 3, 1991, pp. 221-230.
WWW Version. 0401 BibRef

Su, T.H.[Tung-Hsin], Chang, R.C.[Ruei-Chuan],
Computing the k-relative neighborhood graphs in Euclidean plane,
PR(24), No. 3, 1991, pp. 231-239.
WWW Version. 0401 BibRef

Sugihara, K.[Kokichi],
Approximation of Generalized Voronoi Diagrams by Ordinary Voronoi Diagrams,
GMIP(55), No. 6, November 1993, pp. 522-yy. BibRef 9311

Ogniewicz, R.L., Kubler, O.,
Hierarchical Voronoi Skeletons,
PR(28), No. 3, March 1995, pp. 343-359.
WWW Version. BibRef 9503

Ogniewica, R.L., and Ilg, M.,
Voronoi Skeletons: Theory and Applications,
CVPR92(63-69).
IEEE Abstract. IEEE Top Reference. BibRef 9200
Earlier: A2, A1:
The application of Voronoi skeletons to perceptual grouping in line images,
ICPR92(III:382-385).
WWW Version. 9208 BibRef

Oishi, Y., Sugihara, K.,
Topology-Oriented Divide-and-Conquer Algorithm for Voronoi Diagrams,
GMIP(57), No. 4, July 1995, pp. 303-314. BibRef 9507

Ogniewicz, R.L., Kubler, O.,
Voronoi Tessellation of Points with Integer Coordinates: Time-Efficient Implementation and Online Edge-List Generation,
PR(28), No. 12, December 1995, pp. 1839-1844.
WWW Version. BibRef 9512

Koplowitz, J., de Leone, J.,
Hierarchical Representation of Chain-Encoded Binary Image Contours,
CVIU(63), No. 2, March 1996, pp. 344-352.
WWW Version. BibRef 9603

Aurenhammer, F., Edelsbrunner, H.,
An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane,
PR(17), No. 2, 1984, pp. 251-257.
WWW Version. 9611 BibRef

Mayya, N., Rajan, V.T.,
Voronoi Diagrams of Polygons: A Framework for Shape Representation,
JMIV(6), No. 4, December 1996, pp. 355-378. 9701 BibRef
Earlier: CVPR94(638-643).
IEEE Abstract. IEEE Top Reference. BibRef

Chou, J.J.,
Voronoi Diagrams for Planar Shapes,
IEEE_CGA(15), No. 2, 1995, pp. 52-59. BibRef 9500

Gotsman, C., and Lindenbaum, M.,
Euclidean Voronoi Labelling on the Multidimensional Grid,
PRL(16), 1995, pp. 409-415. BibRef 9500

Arcelli, C., Sanniti di Baja, G.,
Computing Voronoi Diagrams in Digital Pictures,
PRL(4), 1986, pp. 383-389. BibRef 8600

Naf, M., Szekely, G., Kikinis, R., Shenton, M.E., Kubler, O.,
3D Voronoi Skeletons and Their Usage for the Characterization and Recognition of 2D Organ Shape,
CVIU(66), No. 2, May 1997, pp. 147-161. 9705
WWW Version. BibRef

Naf, M., Kubler, O., Kikinis, R., Shenton, M.E., Szekely, G.,
Characterization and Recognition of 3D Organ Shape in Medical Image Analysis Using Skeletonization,
MMBIA96(MEDIAL AXES) BibRef 9600

Haidar, H., Bouix, S., Levitt, J.J., Mccarley, R.W., Shenton, M.E., Soul, J.S.,
Characterizing the Shape of Anatomical Structures With Poisson's Equation,
MedImg(25), No. 10, October 2006, pp. 1249-1257.
WWW Version. 0609 BibRef

Fukushima, S.[Shigehiro],
Division-Based Analysis Of Symmetry And Its Application,
PAMI(19), No. 2, February 1997, pp. 144-148.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9703 Delaunay. Voronoi. DAS determines the symmetric axis and the symmetric point pairs on the curve using the duality of the Delaunay triangulation and the Voronoi diagram. BibRef

Sequeira, R.E., Preteux, F.J.,
Discrete Voronoi Diagrams and the Skiz Operator: A Dynamic Algorithm,
PAMI(19), No. 10, October 1997, pp. 1165-1170.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9710 BibRef

Guan, W.G.[Wei-Guang], Ma, S.D.[Song-De],
A List Processing Approach to Compute Voronoi Diagrams and the Euclidean Distance Transform,
PAMI(20), No. 7, July 1998, pp. 757-761.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9808Voronoi from segments lists of rows (run length codes?). BibRef

Amenta, N., Bern, M., Kamvysselis, M.,
A New Voronoi-Based Surface Reconstruction Algorithm,
SIGGraph-98(415-421). BibRef 9800

Fabbri, R., Estrozi, L.F., da Fontoura Costa, L.,
On Voronoi Diagrams and Medial Axes,
JMIV(17), No. 1, July 2002, pp. 27-40.
WWW Version. 0211 BibRef

Farin, G.E.,
Surfaces over Dirichlet tessellations,
CAGD(7), 1990, pp. 281-292. BibRef 9000

Gross, L., Farin, G.E.,
A transfinite form of Sibson's interpolant,
DiscAppMath(93), 1999, pp. 33-50. See also vector identity for the Dirichlet tessellation, A. BibRef 9900

Hiyoshi, H., Sugihara, K.,
Voronoi-based interpolation with higher continuity,
ConferenceSymposium on Computational Geometry, 2000, pp. 242-250. BibRef 0001

Sugihara, K.,
Surface interpolation based on new local coordinates,
CAD(13), No. 1, 1999, pp. 51-58. BibRef 9900

Cohen, L.D.[Laurent D.],
Minimal Paths and Fast Marching Methods for Image Analysis,
MMCV05(xx-yy).
PDF Version. BibRef 0500

Du, Q.[Qiang], Gunzburger, M.[Max], Ju, L.[Lili], Wang, X.Q.[Xiao-Qiang],
Centroidal Voronoi Tessellation Algorithms for Image Compression, Segmentation, and Multichannel Restoration,
JMIV(24), No. 2, March 2006, pp. 177-194.
WWW Version. 0605 BibRef

Browne, M.[Matthew],
A geometric approach to non-parametric density estimation,
PR(40), No. 1, January 2007, pp. 134-140.
WWW Version. 0611Centroidal; Voronoi; Tessellation; Non-parametric; Density estimation BibRef

Morrison, P.[Paul], Zou, J.J.[Ju Jia],
Triangle refinement in a constrained Delaunay triangulation skeleton,
PR(40), No. 10, October 2007, pp. 2754-2765.
WWW Version. 0707Skeletonisation; Constrained Delaunay triangulation; Skeleton refinement; Thinning; Medial axis; Binary image processing; Cartoon image processing BibRef

Jones, T.R.[Thouis R.], Durand, F.[Frédo], Desbrun, M.[Mathieu],
Non-iterative, feature-preserving mesh smoothing,
TOG(22), No. 3, July 2003, pp. xx-yy.
WWW Version. BibRef 0307

Reitsma, R.[René], Trubin, S.[Stanislav], Mortensen, E.[Eric],
Weight-proportional Space Partitioning Using Adaptive Voronoi Diagrams,
GeoInfo(11), No. 3, September 2007, pp. 383-405.
WWW Version. 0709 BibRef

Wang, X.Z.[Xiu-Zhong], Devarajan, V.[Venkat],
Improved 2D mass-spring-damper model with unstructured triangular meshes,
VC(24), No. 1, January 2008, pp. 57-75.
WWW Version. 0712 BibRef

Hu, Z.L.[Zhi-Lan], Yan, H.[Hong], Lin, X.G.[Xing-Gang],
Clothing segmentation using foreground and background estimation based on the constrained Delaunay triangulation,
PR(41), No. 5, May 2008, pp. 1598-1609.
WWW Version. 0711Graph cuts; Constrained Delaunay triangulation; Clothing segmentation; Torso detection BibRef

Liu, D.Q.[Dong-Quan], Nosovskiy, G.V.[Gleb V.], Sourina, O.[Olga],
Effective clustering and boundary detection algorithm based on Delaunay triangulation,
PRL(29), No. 9, 1 July 2008, pp. 1261-1273.
WWW Version. 0711Clustering algorithms; Data mining; Delaunay triangulation BibRef

Nosovskiy, G.V.[Gleb V.], Liu, D.Q.[Dong-Quan], Sourina, O.[Olga],
Automatic clustering and boundary detection algorithm based on adaptive influence function,
PR(41), No. 9, September 2008, pp. 2757-2776.
WWW Version. 0806Clustering algorithms; Data mining; Density-based clustering BibRef

Nonato, L.G.[Luis Gustavo], Lizier, M.A.S., Batista, J., de Oliveira, M.C.F., Castelo, A.,
Topological triangle characterization with application to object detection from images,
IVC(26), No. 8, 1 August 2008, pp. 1081-1093.
WWW Version. 0806Object detection; Object modeling from images; Topological triangle characterization; Morse operators; 2D triangular meshes BibRef

Hahmann, S.[Stefanie], Bonneau, G.P.[Georges-Pierre], Caramiaux, B.[Baptiste],
Bicubic G1 Interpolation of Irregular Quad Meshes Using a 4-Split,
GMP08(xx-yy).
WWW Version. 0804 BibRef

Lehner, B.[Burkhard], Umlauf, G.[Georg], Hamann, B.[Bernd],
Image Compression Using Data-Dependent Triangulations,
ISVC07(I: 351-362).
WWW Version. 0711 BibRef

Hlawitschka, M.[Mario], Scheuermann, G.[Gerik], Hamann, B.[Bernd],
Interactive Glyph Placement for Tensor Fields,
ISVC07(I: 331-340).
WWW Version. 0711 BibRef

Hlawitschka, M.[Mario], Scheuermann, G.[Gerik], Anwander, A.[Alfred], Knösche, T.[Thomas], Tittgemeyer, M.[Marc], Hamann, B.[Bernd],
Tensor Lines in Tensor Fields of Arbitrary Order,
ISVC07(I: 341-350).
WWW Version. 0711 BibRef

Kohout, J.[Josef],
On Digital Image Representation by the Delaunay Triangulation,
PSIVT07(826-840).
WWW Version. 0712 BibRef

Josephson, K.[Klas], Kahl, F.[Fredrik],
Triangulation of Points, Lines and Conics,
SCIA07(162-172).
WWW Version. 0706 BibRef

Bobach, T., Bertram, M., Umlauf, G.,
Issues and Implementation of C1 and C2 Natural Neighbor Interpolation,
ISVC06(II: 186-195).
WWW Version. 0611Extend Hiyoshi and Sugihara ( See also Voronoi-based interpolation with higher continuity. ). , and Sibson and Farin. See also vector identity for the Dirichlet tessellation, A. and See also transfinite form of Sibson's interpolant, A. BibRef

Karavelas, M.[Menelaos], Yvinec, M.[Mariette],
The Voronoi Diagram of Convex Objects in the Plane,
INRIARR-5023, 2003.
HTML Version. BibRef 0300

Alvarez Cascos, I., Yang, Y.Y.[Yong-Yi],
Least-squares mesh model for image compression,
ICIP04(II: 1073-1076).
WWW Version. 0505 BibRef

Gouaillard, A., Gelas, A., Valetle, S., Boix, E., Kanai, T., Prost, R.,
Remeshing algorithm for multiresolution prior model in segmentation,
ICIP04(IV: 2753-2756).
WWW Version. 0505 BibRef

Kato, T., Wada, T.,
Direct condensing: an efficient voronoi condensing algorithm for nearest neighbor classifiers,
ICPR04(III: 474-477).
WWW Version. 0409 BibRef

Cardenes, R., Warfield, S.K., Mewes, A.J.U., Ruiz-Alzola, J.,
K-voronoi diagrams computing in arbitrary domains,
ICIP03(II: 941-944).
IEEE Abstract. IEEE Top Reference. 0312 BibRef

Valette, S.[Sebastien], Kim, Y.S.[Yun-Sang], Jung, H.Y.[Ho-Youl], Magnin, I.E.[Isabelle E.], Prost, R.[Remy],
A multiresolution Wavelet Scheme for Irregularly Subdivided 3D Triangular Mesh,
ICIP99(I:171-174).
IEEE Abstract. IEEE Top Reference. BibRef 9900

Bertin, E., Chassery, J.M.,
3-D Voronoi diagram: application to segmentation,
ICPR92(III:197-200).
WWW Version. 9208 BibRef

Melkemi, M., Chassery, J.M.,
Edge-region segmentation process based on generalized Voronoi diagram representation,
ICPR92(III:323-326).
WWW Version. 9208 BibRef

Rom, H., Peleg, S.,
Image Representation Using Voronoi Tessellation: Adaptive and Secure,
CVPR88(282-285).
IEEE Abstract. IEEE Top Reference. BibRef 8800

Chapter on 2-D Feature Analysis, Extraction and Representations, Shape, Skeletons, Texture continues in
Contour Coding, Boundary Coding .