VORONOI DIAGRAM OF POLYGONAL CHAINS UNDER THE DISCRETE FRÉCHET DISTANCE

DOI10.1142/S0218195910003396zbMath1203.65038MaRDI QIDQ4931733

Binhai Zhu, Maike Buchin, Kevin Buchin, Sergey Bereg, Marina L. Gavrilova

Publication date: 30 September 2010

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

pattern recognitioncomputer graphicsVoronoi diagramcombinatorial complexitypolygonal chainFréchet distancepolygonal curveprotein structure alignmentdiscrete Fréchet distancecontinuous Fréchet distance

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Protein sequences, DNA sequences (92D20)

Cites Work

• Near-linear time approximation algorithms for curve simplification
• Voronoi diagrams and arrangements
• Almost tight upper bounds for lower envelopes in higher dimensions
• Computing Envelopes in Four Dimensions with Applications
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES