A Novel Two-Dimensional Distance Metric to Generalize Manhattan Distance

• 영문명: A Novel Two-Dimensional Distance Metric to Generalize Manhattan Distance
• 발행기관: 한국컴퓨터게임학회
• 저자명: 조청운
• 간행물 정보: 『한국컴퓨터게임학회논문지』제36권 3호, 27~35쪽, 전체 9쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2023.09.30

국문 초록

거리는 기하학과 수학, 물리학 등의 분야에서 기초가 되는 정의다. 매우 근본적인 metric이기 때문에 새로운 정의를 하는 것은 쉽지 않다. 본 연구에서는 기존에 사용되는 거리의 개념을 분석하고 기존의 거리 개념에서 주로 사용되는 거리 개념인 Euclidean distance와 Manhattan distance를 일반화 할 수 있도록 제안한다. Chebyshev distance와 함께 기존에 일반화의 개념으로 사용하는 Minkowski distance의 정의와 이를 이용한 거리개념을 사용할 경우의 단점을 제시한다. 기존의 Manhattan distance가 단순히 각각의 축 방향의 거리를 더한 개념으로 해석하지 않고 4축 방향에 대해 측정한 거리로 해석하는 새로운 관점을 도입하여 본 연구에서는 2차원에서의 새로운 거리 개념을 도입한다. 이는 유클리드 거리와 맨하탄 거리를 일반화하는 개념으로, 제안된 거리 개념을 기하학적인 측면에서 도출하고 이를 계산하는 알고리즘을 제시하였다. 우리는 기존의 사용되는 거리 개념을 적용하여 2차원 상에서 랜덤하게 분포하는 점들로부터 최단거리에 의한 Voronoi 영역을 생성하는 결과를 통해 차이를 비교하였다. 제안된 방법은 거리개념을 사용하는 다양한 그래픽스 알고리즘의 분야에 응용하여 확장 할 수 있을 것으로 기대한다.

영문 초록

Distance is a fundamental definition in fields such as geometry, mathematics, and physics. Because it is a very fundamental metric, it is not easy to create a new definition. In this study, we analyze existing distance definition and propose to generalize Euclidean distance and Manhattan distance, which are mainly used distance metric in existing distance definition. We analyze the definition of Minkowski distance, which is previously used as a concept of generalization along with Chebyshev distance, and the disadvantages of using this distance metric. By introducing a new perspective that interprets the existing Manhattan distance as a distance measured in four axes rather than simply adding the distances in each axis direction, this research introduces a new distance metric in two dimensions. This is a metric that generalizes the Euclidean distance and the Manhattan distance, and the proposed distance metric is derived from a geometrical aspect and an algorithm for calculating it is presented. We applied the existing distance definition and compared the differences through the results of generating a Voronoi area by the shortest distance from randomly distributed points in two dimensions. It is expected that the proposed method can be applied and expanded to the field of various graphics algorithms that use the distance metric.

목차

1. Introduction

2. Literature review

3. Proposed Method

4. Experimental Results and Review

5. Conclusion

Reference

키워드

Distance Metric Manhattan Distance Euclidean Distance Minkowski distance