본 논문에서 우리는 평면상에 점들이 주어지는 경우에, 조각적 이차 다항식 곡선으로 맞추는 문제를 다룬다. 곡선은 이차 다항식 선분들로 이루어지고, 하나의 선분은 두 점 사이를 연결한다. 하지만 이 곡선은 점들의 부분집합만을 지나고, 지나지 못하는 점들에 대해서는 $L^{\infty}$거리로 에러를 측정한다. 이 문제에 대해서 우리는 두 가지 최적화 문제를 생각한다. 첫째로 허용 가능한 에러의 범위가 주어지고, 곡선 선분의 개수를 줄이는 문제이고, 둘째로 선분의 개수가 주어지고, 에러를 줄이는 문제이다. 주어진 점들의 개수 n에 대해서, 우리는 첫번째 문제에 대한 $O(n^2)$알고리즘과 두번째 문제에 대한 $O(n^3)$ 알고리즘을 제안한다.
본 논문에서 우리는 평면상에 점들이 주어지는 경우에, 조각적 이차 다항식 곡선으로 맞추는 문제를 다룬다. 곡선은 이차 다항식 선분들로 이루어지고, 하나의 선분은 두 점 사이를 연결한다. 하지만 이 곡선은 점들의 부분집합만을 지나고, 지나지 못하는 점들에 대해서는 $L^{\infty}$거리로 에러를 측정한다. 이 문제에 대해서 우리는 두 가지 최적화 문제를 생각한다. 첫째로 허용 가능한 에러의 범위가 주어지고, 곡선 선분의 개수를 줄이는 문제이고, 둘째로 선분의 개수가 주어지고, 에러를 줄이는 문제이다. 주어진 점들의 개수 n에 대해서, 우리는 첫번째 문제에 대한 $O(n^2)$ 알고리즘과 두번째 문제에 대한 $O(n^3)$ 알고리즘을 제안한다.
In this paper, we study the problem to fit a piecewise-quadratic polynomial curve to points in the plane. The curve consists of quadratic polynomial segments and two points are connected by a segment. But it passes through a subset of points, and for the points not to be passed, the error between th...
In this paper, we study the problem to fit a piecewise-quadratic polynomial curve to points in the plane. The curve consists of quadratic polynomial segments and two points are connected by a segment. But it passes through a subset of points, and for the points not to be passed, the error between the curve and the points is estimated in $L^{\infty}$ metric. We consider two optimization problems for the above problem. One is to reduce the number of segments of the curve, given the allowed error, and the other is to reduce the error between the curve and the points, while the curve has the number of segments less than or equal to the given integer. For the number n of given points, we propose $O(n^2)$ algorithm for the former problem and $O(n^3)$ algorithm for the latter.
In this paper, we study the problem to fit a piecewise-quadratic polynomial curve to points in the plane. The curve consists of quadratic polynomial segments and two points are connected by a segment. But it passes through a subset of points, and for the points not to be passed, the error between the curve and the points is estimated in $L^{\infty}$ metric. We consider two optimization problems for the above problem. One is to reduce the number of segments of the curve, given the allowed error, and the other is to reduce the error between the curve and the points, while the curve has the number of segments less than or equal to the given integer. For the number n of given points, we propose $O(n^2)$ algorithm for the former problem and $O(n^3)$ algorithm for the latter.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
실제 CAD/CAM, 컴퓨터 그래픽스등과 같은 응용 분야에서 사용되는 곡선들은 대부분 이차 이상의 다항식 곡선들이 사용된다. 따라서 이차 이상의 다항식 곡선들로 점들을 맞추는 알고리즘을 분석하는 것이 의미 있는 일이며, 이 논문에서는 이차 다항식 곡선으로 점들을 맞추는 문제를 다룰 것이다.
이전 연구들에서는 조각적 일차 다항식 곡선, 즉, 직선 선분들을 가지는 곡선만을 다루었다. 본 논문에서는 각 선분들이 이차 다항식으로 이루어진 곡선을 다룰 것이다.
우리는 본 논문에서 평면에 점들이 주어지고, 조각적이 차 다항식 곡선으로 맞추는 문제를 연구하였다. 특별히 두 가지 최적화 문제를 다루었는데, 첫번째로 에러의 범위 e 이 주어질 때, 점들과 곡선의 L" 거리가 e 보다 작거나 같으면서 곡선의 최소 선분을 구하는 min-# 문제이고, 두번째로 곡선의 선분의 개수 k>0 가 주어질 때, 점들과 곡선의 거리의 최소값을 찾는 min” 문제이다.
편의상으로, pi를 주어진 점뿐만 아니라 대응되는 지름길 그래프의 노드를 나타낸다고 하자. 임의의 노드 Pi 로부터 연결되는 에지들을 생각할 것이다.
가설 설정
이 문제를 min皿# 문제라고 부를 것이다. 둘째로 우리는 선분의 개수 k 가 입력으로 주어지고, 左보다 쟉거나 같은 개수의 선분을 가지는 곡선 중에 점들과 곡선 사이의 에러를 최소화 하는 곡선을 찾을 것이다. 이 문제를 min-e 문제라고 부를 것이다.
와 邛 를 지나는 이차 다항식 /'(X)가 가질 수 있는 에러의 최소값을 말한다. 우리는 각각의 점 Pi 와 Pi 쌍에 대해서 에러 상수 %를 계산할 것이다. 이차 다항식 f(X)는 점 邛 와 P, 를 지나므로, f(X)는 다음과 같이 하나의 미지수 a의 함수로 쓸 수 있다.
제안 방법
하지만 계산기하학 분야에서는 알고리즘의 시간 복잡도 계산과 같은 분석을 통해 다루었고, 대부분은 조각적 일차 다항식 곡선, 다시 말해, 직선 선분들로 이루어진 일종의 경로들을 다루었다. 이 경로와 점 들 사이의 에러를 L" 또는 L2 거리로 측정하고, 이차원 또는 삼차원 공간에서의 문제들을 다루었다.
다음 노드 pJ+i 로의 에지를 생각할 때, 곡선이 점 邛에서 에러 범위 안에 지난다는 조건으로 만들어 지는 회랑이 추가되고, 이는 쌍대 평면에서 수직 선분이 추가됨을 말한다. 그리고 곡선이 점 0T를 지난다는 조건의 직선은 쌍대 평면에서의 점에 대응되고 수직 선분들을 모두 지나고 이 점을 지나는 직선이 존재하는지 테스트함으로써, 노드 ft+1 로의 에지의 존재여부를 결정한다.
있다. 따라서, 2.1 절에서 풀었던 min-# 문제의 알고리즘을 사용해서 모든 勺에 대해서 이진 검색(binary search)을 수행한다. 다시 말해서, %을 크기 순으로 정렬시킨 후, 이것을 引 二 … 三 跖으로 나타낸다고 흐}자.
본 논문에 서는 평 면상에 Z2개 의 점 Pi (Xi, yi), XI < X2 < -<Xn, 들의 집합 〃가 주어질 때, 이 점들을 잘 맞추는 조각적 이차 다항식 곡선(piecewise-quadratic polynomial curve)을 찾는 문제를 생각한다. 이 문제는 CAD/CAM, CAGD(Computer Aided Geometric Design), 컴퓨터 그래픽스 등의 분야에서 자주 나타난다.
우리는 min냬와 miir* 문제에 대해서, 각각의 알고리즘을 제안하였고. 시간 복잡도 분석을 통해서 각각 。(打2)과 0(疽) 시간을 가짐을 보였다,
성능/효과
위의 설명을 종합해보면, 노드 p, 에서 출발하는 에지들의 존재를 테스트하기 위해서, 노드 ft, j>i 들을 순차적으로(incrementally) 고려한다. 노드 p/로의 에지의 존재 여부가 막 결정되었다고 가정하자.
특별히 두 가지 최적화 문제를 다루었는데, 첫번째로 에러의 범위 e 이 주어질 때, 점들과 곡선의 L" 거리가 e 보다 작거나 같으면서 곡선의 최소 선분을 구하는 min-# 문제이고, 두번째로 곡선의 선분의 개수 k>0 가 주어질 때, 점들과 곡선의 거리의 최소값을 찾는 min” 문제이다. 이 문제들욘 CAD/CAM, 컴퓨터 그래픽스 등에 응용될 수 있는데, min냬 문제는 최소 선분의 곡선 을 찾아서, 곡션의 저장 공간을 최소화 할 수 있고, min-£ 문제는 점들을 잘 맞추는 근사 곡선을 찾을 수 있다.
참고문헌 (6)
S. L. Hakimi and E. F. Schmeichel. "Fitting polygonal unctions to a set of points in the plane," Computer Vision, Graphics, and Image Processing, Vol. 53, 132-136, 1991.
K. R. Varadarajan. "Approximating monotone ploygonal curves using the uniform metric," In Proc. of 12th ACM Symposium on Computational Geometry, 311-318, 1996.
H. Imai and M. Iri, "Computational-geometric methods for polygonal appoximations of a curve," Computer Vision, Graphics, and Image Processing, Vol.36, 31-41, 1986.
W. S. Chan and F. Chin. " Approximation of polygonal curves with minimum number of line segments or minimum error," Int. J. of Computational Geometry and Applications, Vol. 6(1), 59-77, 1996.
G. Barequet, D. Z. Chen, O, Daescu, M.T. Goodrich, and J. Snoeyink. "Efficiently approximating polygonal paths in three and higher dimensions," In Proc. of 14th ACM Symposium on Computational Geometry, 317-326, 1998.
F. P. Preparata and M. I. Shamos. "Computational geometry: An introduction, " Springer-Verlag, 1985.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.