Scholarlink

<p>The Hausdorff distance is a measure of the similarity between two sets of points. It has been used in many different fields, such as comparing MRI images or transportation routes. There have been different approaches to compute the Hausdorff distance; some algorithms operate in main memory, while others store the set of points in secondary memory. In order to avoid secondary memory, compact data structures, such as <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10707_2025_557_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\(\varvec{k^2\text {-tree}}\)</EquationSource> </InlineEquation>, can be used. They are able to index large sets of points in main memory, and they can be efficiently queried while minimizing storage. We present in this article two efficient algorithms (<span>HDKP1</span> and <span>HDKP2</span>) to compute the Hausdorff distance over two data sets that are stored in <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10707_2025_557_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\(\varvec{k^2\text {-tree}}\)</EquationSource> </InlineEquation>s. These algorithms provide a time- and space-efficient solution. The performance of our algorithms was evaluated through a series of experiments together with the most promising algorithms from the state of the art. Based on the results, it was concluded that our approach is competitive or exceeds current algorithms.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Efficient algorithms to calculate the Hausdorff distance on point sets represented by a \(k^2\text {-tree}\)

  • 期刊论文

  • 发表日期：

    2025年8月29日

查看全文
  • Fernando Domínguez,
  • Gilberto Gutiérrez,
  • Miguel R. Penabad,
  • Miguel Romero,
  • Fernando Santolaya

摘要

The Hausdorff distance is a measure of the similarity between two sets of points. It has been used in many different fields, such as comparing MRI images or transportation routes. There have been different approaches to compute the Hausdorff distance; some algorithms operate in main memory, while others store the set of points in secondary memory. In order to avoid secondary memory, compact data structures, such as \(\varvec{k^2\text {-tree}}\) , can be used. They are able to index large sets of points in main memory, and they can be efficiently queried while minimizing storage. We present in this article two efficient algorithms (HDKP1 and HDKP2) to compute the Hausdorff distance over two data sets that are stored in \(\varvec{k^2\text {-tree}}\) s. These algorithms provide a time- and space-efficient solution. The performance of our algorithms was evaluated through a series of experiments together with the most promising algorithms from the state of the art. Based on the results, it was concluded that our approach is competitive or exceeds current algorithms.