7.7.2 Voronoi Diagrams, Delaunay Triangulation, 2-D Meshes

Chapter Contents (Back)
Voronoi Diagrams. Delaunay Triangulation. Mesh, 2-D. Triangulation.
See also Triangulated Surface Models, Mesh Models, Mesh Descriptions, 3-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.
WWW Link. 0410
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 Link. Theory behind the Delaunay triangulation. Theory necessary to construct and manipulate triangulations. BibRef 0600

Boissonnat, J.D.[Jean-Daniel], Pons, J.P.[Jean-Philippe], Yvinec, M.[Mariette],
From Segmented Images to Good Quality Meshes Using Delaunay Refinement,
ETVC08(13-37).
Springer DOI 0811
BibRef

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., 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.[Narendra], An, B.[Byong], Schachter, B.[Bruce],
Image Representation Using Voronoi Tessellation,
CVGIP(29), No. 3, 1985, pp. 286-295.
Elsevier DOI BibRef 8500
Earlier: A2, A1, Only:
Representation of Images Using Voronoi Tessellation,
CVPR83(188-189). Tessellation drived from Poisson point process, for transmission. BibRef

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.
Elsevier DOI 0309
Construct 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.
Elsevier DOI 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.
Elsevier DOI 0401
BibRef

Kooshesh, A.A., Moret, B.M.E.,
Three-coloring the vertices of a triangulated simple polygon,
PR(25), No. 4, April 1992, pp. 443.
Elsevier DOI 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.
Elsevier DOI first regularize Voronoi diagram then skeleton. BibRef 9503

Ogniewicz, R.L., Ilg, M.,
Voronoi Skeletons: Theory and Applications,
CVPR92(63-69).
IEEE DOI BibRef 9200
Earlier: A2, A1:
The application of Voronoi skeletons to perceptual grouping in line images,
ICPR92(III:382-385).
IEEE DOI 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.
Elsevier DOI BibRef 9512

Koplowitz, J., de Leone, J.,
Hierarchical Representation of Chain-Encoded Binary Image Contours,
CVIU(63), No. 2, March 1996, pp. 344-352.
DOI Link 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.
Elsevier DOI 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 DOI BibRef

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

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

Arcelli, C.[Carlo], Sanniti di Baja, G.[Gabriella],
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.
DOI Link 9705
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.
IEEE DOI 0609
BibRef

Fukushima, S.[Shigehiro],
Division-Based Analysis Of Symmetry And Its Application,
PAMI(19), No. 2, February 1997, pp. 144-148.
IEEE DOI 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 DOI 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 DOI 9808
Voronoi 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.
DOI Link 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 File. BibRef 0500

Du, Q.A.[Qi-Ang], 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.
Springer DOI 0605
BibRef

Wang, J., Ju, L.[Lili], Wang, X.Q.[Xiao-Qiang],
An Edge-Weighted Centroidal Voronoi Tessellation Model for Image Segmentation,
IP(18), No. 8, August 2009, pp. 1844-1858.
IEEE DOI 0907
BibRef

Wang, J., Ju, L.[Lili], Wang, X.Q.[Xiao-Qiang],
Image Segmentation Using Local Variation and Edge-Weighted Centroidal Voronoi Tessellations,
IP(20), No. 11, November 2011, pp. 3242-3256.
IEEE DOI 1110
For images with color distributions or inhomogeneous intensity.
See also 3D Superalloy Grain Segmentation Using a Multichannel Edge-Weighted Centroidal Voronoi Tessellation Algorithm. BibRef

Wang, J.[Jie], Wang, X.Q.[Xiao-Qiang],
VCells: Simple and Efficient Superpixels Using Edge-Weighted Centroidal Voronoi Tessellations,
PAMI(34), No. 6, June 2012, pp. 1241-1247.
IEEE DOI 1205
Edge weighted voronoi tesselation. Generate oversegmentation of the image then get local boundaries. BibRef

Browne, M.[Matthew],
A geometric approach to non-parametric density estimation,
PR(40), No. 1, January 2007, pp. 134-140.
Elsevier DOI 0611
Centroidal; 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.
Elsevier DOI 0707
Skeletonisation; 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 Link. 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.
Springer DOI 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.
Springer DOI 0712
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.
Elsevier DOI 0711
Clustering 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.
Elsevier DOI 0806
Clustering 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.
Elsevier DOI 0806
Object detection; Object modeling from images; Topological triangle characterization; Morse operators; 2D triangular meshes BibRef

Cuadros-Vargas, A.J., Lizier, M.A.S., Minghim, R., Nonato, L.G.,
Generating Segmented Quality Meshes from Images,
JMIV(33), No. 1, January 2009, pp. xx-yy.
Springer DOI 0804
BibRef

Lizier, M.A.S.[Mario A.S.], Martins, Jr., D.C.[David C.], Cuadros-Vargas, A.J.[Alex J.], Cesar, Jr., R.M.[Roberto M.], Nonato, L.G.[Luis G.],
Generating segmented meshes from textured color images,
JVCIR(20), No. 3, April 2009, pp. 190-203.
Elsevier DOI 0903
Mesh generation; Delaunay triangulation; Feature evaluation and selection; Texture classification; W-operators; Texture segmentation; Imesh image; Mesh modeling; Mesh generation from image data; Mesh segmentation BibRef

Josephson, K.[Klas], Kahl, F.[Fredrik],
Triangulation of Points, Lines and Conics,
JMIV(32), No. 2, October 2008, pp. xx-yy.
Springer DOI 0804
BibRef
Earlier: SCIA07(162-172).
Springer DOI 0706
BibRef

Schlei, B.R.,
A new computational framework for 2D shape-enclosing contours,
IVC(27), No. 6, 4 May 2009, pp. 637-647.
Elsevier DOI 0904
Contour; Isocontour; Edge; Unstructured grid; Delaunay tessellation; Skeleton; Shape morphology; Material surface; Bacterial colony; Handwritten letter recognition; Constellation; Freeze-out hyper-surface BibRef

Pan, J., Wang, M., Li, D., Li, J.L.[Jun-Li],
Automatic Generation of Seamline Network Using Area Voronoi Diagrams With Overlap,
GeoRS(47), No. 6, June 2009, pp. 1737-1744.
IEEE DOI 0905
BibRef

Pan, J.[Jun], Wang, M.[Mi], Ma, D.[Di], Zhou, Q.H.[Qing-Hua], Li, J.L.[Jun-Li],
Seamline Network Refinement Based on Area Voronoi Diagrams With Overlap,
GeoRS(52), No. 3, March 2014, pp. 1658-1666.
IEEE DOI 1403
geophysical image processing BibRef

de Moura Pinto, F.[Francisco], Dal Sasso Freitas, C.M.[Carla Maria],
Dynamic Voronoi diagram of complex sites,
VC(27), No. 6-8, June 2011, pp. 463-472.
WWW Link. 1107
BibRef

Adams, M.D.[Michael D.],
A Flexible Content-Adaptive Mesh-Generation Strategy for Image Representation,
IP(20), No. 9, September 2011, pp. 2414-2427.
IEEE DOI 1109
BibRef
And:
An incremental/decremental Delaunay mesh-generation framework for image representation,
ICIP11(189-192).
IEEE DOI 1201
BibRef
Earlier:
An improved content-adaptive mesh-generation method for image representation,
ICIP10(873-876).
IEEE DOI 1009
BibRef
Earlier:
An evaluation of several mesh-generation methods using a simple mesh-based image coder,
ICIP08(1041-1044).
IEEE DOI 0810
BibRef

Li, P., Adams, M.D.[Michael D.],
A Tuned Mesh-Generation Strategy for Image Representation Based on Data-Dependent Triangulation,
IP(22), No. 5, May 2013, pp. 2004-2018.
IEEE DOI 1304
BibRef

Beristain, A.[Andoni], Graña, M.[Manuel], Gonzalez, A.I.[Ana I.],
A Pruning Algorithm for Stable Voronoi Skeletons,
JMIV(42), No. 2-3, February 2012, pp. 225-237.
WWW Link. 1202
BibRef

Bae, S.W.[Sang Won],
On Linear-Sized Farthest-Color Voronoi Diagrams,
IEICE(E95-D), No. 3, March 2012, pp. 731-736.
WWW Link. 1203
BibRef

Ayala, R.[Rafael], Fernández-Ternero, D.[Desamparados], Vilches, J.A.[José Antonio],
Perfect discrete Morse functions on 2-complexes,
PRL(33), No. 11, 1 August 2012, pp. 1495-1500.
Elsevier DOI 1206
BibRef
And:
Perfect Discrete Morse Functions on Triangulated 3-Manifolds,
CTIC12(11-19).
Springer DOI 1206
Perfect discrete Morse function; Pseudomanifold; Graph; Betti numbers BibRef

Battaglino, D.[Daniela], Frosini, A.[Andrea], Rinaldi, S.[Simone],
A decomposition theorem for homogeneous sets with respect to diamond probes,
CVIU(117), No. 4, April 2013, pp. 319-325.
Elsevier DOI 1303
BibRef
Earlier:
Planar Configurations Induced by Exact Polyominoes,
IWCIA11(275-283).
Springer DOI 1105
Discrete tomography; Diamonds; Tiling BibRef

Attene, M.[Marco], Campen, M.[Marcel], Kobbelt, L.[Leif],
Polygon mesh repairing: An application perspective,
Surveys(45), No. 2, February 2013, pp. Article No 15.
DOI Link 1303
Survey, Mesh. BibRef

Guo, J.W.[Jian-Wei], Yan, D.M.[Dong-Ming], Bao, G.B.[Guan-Bo], Dong, W.M.[Wei-Ming], Zhang, X.P.[Xiao-Peng], Wonka, P.[Peter],
Efficient triangulation of Poisson-disk sampled point sets,
VC(30), No. 6-8, June 2014, pp. 773-785.
Springer DOI 1407
BibRef

Browne, M.[Matthew],
Regularized tessellation density estimation with bootstrap aggregation and complexity penalization,
PR(45), No. 4, 2012, pp. 1531-1539.
Elsevier DOI 1410
Regularization BibRef

Ying, S.[Shen], Xu, G.[Guang], Li, C.P.[Cheng-Peng], Mao, Z.Y.[Zheng-Yuan],
Point Cluster Analysis Using a 3D Voronoi Diagram with Applications in Point Cloud Segmentation,
IJGI(4), No. 3, 2015, pp. 1480.
DOI Link 1511
BibRef

Wang, J.[Jue], Kwan, M.P.[Mei-Po],
Hexagon-Based Adaptive Crystal Growth Voronoi Diagrams Based on Weighted Planes for Service Area Delimitation,
IJGI(7), No. 7, 2018, pp. xx-yy.
DOI Link 1808
BibRef

Yuan, X.X.[Xi-Xi], Cai, Z.C.[Zhan-Chuan],
An Adaptive Triangular Partition Algorithm for Digital Images,
MultMed(21), No. 6, June 2019, pp. 1372-1383.
IEEE DOI 1906
Partitioning algorithms, Image coding, Heuristic algorithms, Image reconstruction, Encryption, Distortion, Image processing, information encryption BibRef

Favreau, J.D.[Jean-Dominique], Lafarge, F.[Florent], Bousseau, A.[Adrien], Auvolat, A.[Alex],
Extracting Geometric Structures in Images with Delaunay Point Processes,
PAMI(42), No. 4, April 2020, pp. 837-850.
IEEE DOI 2003
Segments, triangles, line networks, polygons. Kernel, Perturbation methods, Markov processes, Task analysis, Image segmentation, image compression BibRef

Li, X.L.[Xiao-Li], Chen, J.S.[Jin-Song], Zhao, L.L.[Long-Long], Guo, S.X.[Shan-Xin], Sun, L.[Luyi], Zhao, X.M.[Xue-Mei],
Adaptive Distance-Weighted Voronoi Tessellation for Remote Sensing Image Segmentation,
RS(12), No. 24, 2020, pp. xx-yy.
DOI Link 2012
BibRef

Chen, B.Y.[Bi Yu], Huang, H.H.[Hui-Huang], Chen, H.P.[Hui-Ping], Liu, W.X.[Wen-Xuan], Chen, X.Y.[Xuan-Yan], Jia, T.[Tao],
Efficient Algorithm for Constructing Order K Voronoi Diagrams in Road Networks,
IJGI(12), No. 4, 2023, pp. 172.
DOI Link 2305
BibRef

Liu, Q.P.[Qing-Ping], Zhao, X.S.[Xue-Sheng], Duan, Y.Z.[Yuan-Zheng], Qin, M.M.[Meng-Meng], Xie, W.[Wenlan], Sun, W.B.[Wen-Bin],
Dynamic Construction of Spherical Raster Voronoi Diagrams Based on Ordered Dilation,
IJGI(13), No. 6, 2024, pp. 202.
DOI Link 2406
BibRef

Melodia, L.[Luciano], Lenz, R.[Richard],
Persistent Homology as Stopping-criterion for Voronoi Interpolation,
IWCIA20(29-44).
Springer DOI 2009
BibRef

Li, X.P.[Xian-Ping],
Anisotropic Mesh Representation for Color Images,
ICIVC20(139-143)
IEEE DOI 2009
Measurement, Tensile stress, Color, Image color analysis, Gray-scale, Image reconstruction, Finite element analysis, color image, finite element interpolation BibRef

Langer, M.[Maximilian], Gabdulkhakova, A.[Aysylu], Kropatsch, W.G.[Walter G.],
Non-centered Voronoi Skeletons,
DGCI19(355-366).
Springer DOI 1905
BibRef