The Computation of the Voronoi Diagram of a Circle Set Using the Voronoi Diagram of a Point Set: II. Geometry

한국

학회

제

6

/ 호

점 집합의 보루 누이 다이어그램을 이용한 원 집합의 보로노이 다이어그램의 계산:

^{기하학적 측면}

김 동욱 * , 김 덕 수 ** , 조동수 * , Kokichi Sugihara

*학생회원,

**종신회원, 한양대학교산업공학과

***University of Tokyo,

Department of

Eng­

ineering and Information Physics

2000.

8

2000.

The Computation of the Voronoi Diagram of a Circle Set Using the Vbronoi Diagram of a Point Set: H. Geometry

Kim, D.*, Kim, D. S.**, Cho, D.* and Sugihara, K.***

ABSTRACT

Presented in this

are algorithms to

positions of vertices and equations

edges of

diagram of

circle set. The

are located

plane,

radii of

circles are not

equal and

circles

not

The

correctly and effi­

ciently work when the correcttopology ofthe Vbronoi

diagram

three

of

vertex

treating

as

plane,

Z-plane, and transforming it

complex plane,

transformation. Then,

­

is

as a

location problem in

by

and

circles in

店plane. And

inverse-transformed

in

from

in

of

Vbronoi vertex.

topology is constructed

of the vertices,

equations of edge

computed in

rational quadratic

form.

Key words: Circle

set voronoi

10th problem,

Rational

Point location problem

1

^{. 서 론}

유클리드 평면에 원들이

있고, 원들의

지름은 같을 필요가

원들이 서로 교차하는

우도 발생한다.

집합이 주어 졌을 때, 보 로노이 다이어그램을 구하려

이와

관련하여 다음과 같은 기존 연구가 존재한 다

그리고 이에 대해서는 이전의

측면에서

보았다

제시한 알고리듬의 기본 아이디어는 다음과 같다.

전처리 과정으

로

보로노이 다이어그램을

이들

보로노이 다이어그램의 위상 정보를 초기해로 놓고

집합

이

가지기

플 립

올바른 위상 정보를 바탕으로 하여

수정한다.

개 수를

할 때, 첫번째 단계에서의 최악의 경우 계 산량은 OEogn)

경우

산량은

)으로

번째 단계가

논

중점적으로 다루고자 하는 문제이다.

구하고자 하는

보로노이

기

요소는 보로노이 꼭지점의 좌표값과

모 서리의

보로노이 꼭지점의 좌표값은

원이 주어지면

수

원은

보로노이 다이어그램의 꼭지점의 위상 정보를 통해

수 있다. 또한 보로노이 꼭지점의 정보는

31

32 김동욱, 김덕수, 조동수,

Kokichi Sugihara

보로노이 모서리의

플립

판단하는 근거가

다.

보로노이 꼭지점의 위치를

하는 것은

알고리듬의 위상 부분과 매우

접한 관계를

원

집합 보로노이 다이어그램에서 보로노이 꼭지 점의 위치의

주어졌을 때

접하는 원을 구하는 문제와 정확히 일치한다. 그리 고

아폴로니우스의

번째 문제로

알려져

F

외접원의

쉽게 생각해서 두 쌍곡선의 교점을

구할 수 있다. 이는 사차 방정식을 해를 구하는 과정을 포함하며,

공식을 이용하거나

과정을

해 를 구할 수

그러나 위의 방법은 매우

하며 수치적으로도 불안정한 것으로 밝혀졌다.

예 로 Mathematica

이용하여 두 쌍곡선의 교점을

연산으로 구한 결과 대략 75,000줄의

코드를

수

이

문제는

2세기 경의

에

처음 제기 되었고

번째 문제로 알려지고 있다.

문제는

공간에서는 매우 복잡한 것으로

복소 공 간을 이용하면 다소

해결할 수

것으로 나 타났다. 복소 공간에서의 뫼비우스

또는

fractional

원을 직선으로 또는 그 역으로 변환하는 것으로

려져있다[

뫼비우스 변환을 통하여,

공통 외접원을 구하는

두

접선을

｝는 문 제로

수

방법은 두 쌍곡선의 교점을 구하는

보다

간단한 것으로 밝혀졌다.

원

집합

모서리는 직선 또 는 쌍곡선의 형태이다03

두

경우 선분이

그

쌍곡선이

Persson과

식을

셋 요소의 교점 방정식을

로 표현하였다

끼. 그들은 직선과 쌍곡선을 서로 다른 형태로

다르게, Kim은

리

포물선, 쌍곡

등의 표현을 하나의 형태로 표현하였다™.

이를

통하여 모서리의 기하 정보를 다루는

등의 응용을 더욱

만들

있다" *

이 논문은 다음과

구성되어 있다. 다음 절에 서는

용어와

을 계산하는 방법을 설명한다. 다음

유리 이 차

형태를 이용하여 모서리의 식을

는

방법을 제시한다.

구현과 실험

를 설명한다.

2

. 용 어

이

절에서는 알고리듬 설명의

필요한 몇몇

용어를

｛미曰,2,..

는

c

중심점

집합을 나타내며, C=

〃

를

c

반지름이라 할 때 c,=(p“

집합을 나 타낸다. VD(P)와

는 각각

집합과

보로노이 다이어그램을 나타낸다.

편의상 모서리와

다른

각각 보로 노이 모서리와 보로노이 꼭지점을

각 모 서리 e

e,

e를 플립했을

나타 낸다.

나타낸다.

설명의

편의를 위해

데이터에 대한

가지 가정을 두었으며

특별한

수

첫번째 가정은

ass"成이라 부르며, VD(P)

모든 꼭지점의 차수는

것을

두 번째 가정은

degenerate circle set assumption^]

라

이

VD(C)의 모든 꼭지점의 차수 또한

것을 의미한다.

다른

는 존재하지

다고 가정하고,

assumpticm이라 부른다.

또한 거리는 유클리드 身

metric을

적용하였다. 그리고, VD(P)

VD(C)

자 료구조는

또는

자료 구조를 사용하는 것으로 가정하였다2

3.

꼭지점의 좌표값

세 개의 원이

주어져있다.

1에서와

원에 동시에 접하는 원이

8개 존재 한다.

1에서

제너레이터 원이고

원은 접하는 원들이다.

각각

나의 외접원,

원에만

(a)

(c) (d)

Fig. 1.

sim니

generator

shown as shaded ones.

한국

CAD/CAM

1 호 2001

월

점

다이어그램을 이용한

집합의

II. 기하학적 측면

Fig.

2.

generator circles and

하나의

원에만

원에 내접 하는 원을

있다.

접원들 중에서, 우리 가 원하는 원은 첫번째

동시에 외접하는

그러나, 주어진 원들에 대해

외접원이 존재하지

경우,

외접원이 존재하는

개의

존재하는

있다(이전 논문의

참고). 그리하여 ,

주어졌을 때

외

존재를

것과 존재할 경우 외접원을

것이 우리의 문제가

3.1 뫼비우스 변환

제너레이터가 놓여있는

복소

즉 유클리드 공간의

점(

y)가 복소수

■心가 된다. 또한, Fig.

2에서와

.y,)

제너레이터 원을

(=1,

하자.

이라 가정하 자. 위의 원들의 반지름을 r,만큼

으로 놓는다.

C3는

가 된다. 이렇게

후, 만약

점 z戶

를 지나고

S

원을 찾을 수 있다면,

c

,

에 동시에

를 단순히

반지 름에서

구할 수

Conformal 매핑은 방향성 있는

사이의 각을 보존하는

매핑 중 다음과 같이 정의되는 뫼비우스

대

<5

복소수 또는

식 (1)

Z■평면의 원과

W-

또는 직선으로 매핑한다. 뫼비우스

가지

태 중

다음과 같은 형태의 변환을

W(z)=— (2)

bZo

식

(2)

주어진 변환은 다음의 특성을 가지는

으로 알려져

여기에서는 논의의 편의상 증 명

특성 L

Z-

zo

직선과 원들은

직선으로 매핑하며, 그 역도 성립한다.

특성 2.

평면의

를

원과 직선들은

평면에서 원으로 매핑되며, 그 역도 성립한다.

특성

3. Z-평면의 무한대에 위치한 점은 M

원점으로 매핑되며, 그 역도 성립한다.

그리하여, Fig. 3

함수 W

만약 Z3가

Z-

과 를 I私평면에서 각각

과 必로 매핑한다.

그래서,

접하는 구하고자 하는

6는

두 원에

직선

매핑될 것이다.

또

주목해야 하는 사실은 Z-평면에서

대의 점과

의

위치하는 점은 모두 외접

외부에

것이다. 그리하여,

살펴본 특성들에

Z-평면에서 6 의 외부에 있던 점은

。와

대해서 같은 쪽에 존재하게

원점과

점이

/에 대해서 같은 쪽에 있어야

가 외접원이 된다

변환

의

특성 때문에,

평면에서

6 는 呼평면에서 두

玷과

에 접하는 직선으로 매핑 된다.

변환

Z-평면의

c,=fa,

평면에

W,,

변환하는

밝혀졌으며, 식은

래와

A

(^-x3

1

3

3

2

Fig.

3. Mobius

W=W(z)=l/(z-

(a)

(b) W-plane.

한국CAD/CAM학회 논문집

제 6

제

2001년

34 김동욱, 김덕수, 조동수,

Kokichi Sugihara

Fig.

4. Inverse

maps from

to

(a)

plane and (b)

W(z)와 비슷한 방식으로

변환 또한

제시할 수

Z

(4)

식 (4) 또한

매핑이며,

점을 지나지

직선은

원으로 매핑한 다.

직선을 的+

1=0

변환된

은

이 고, 반지름은

2

3.2 여러 개의 접원 중 내접원 구하기

Fig.

4(a)에서와

卬평면에서의 두

"가

때, 두 원에

접하는

가지가

4(a)

점을 呼평면에서의 원점이라고 하자. 그러면,

은 Fig.

와

평면에서

로 매핑된다.

"과

원점

에

같은 쪽에 위치해

때

동시에

원으로 매핑되었다.

비 슷하게, 직선

두 원이 Z-

무한대와 반대편에

공통

'로

다.

Z과

는

차이가

이 는

같은

다른 쪽에

있어서

원에 대해서는 외접하

또 다른 한 원에 대해서는 내접한다. 그리하여,

과 乙4는 각각

그리하여, 매핑 되었을

외접원이 되는

에서의

乙은 하나 또는 두

접하 는

또는

가 된다.

주어

두

접원을 찾는 문제는

두

접선을 찾는

두

두

W과 Wz,

점。가

직선에 대해서 같은 반평면에 속하게되

는 직선이 Z-

외접원으로 매핑된다.

외접원이

수도

하나 또는 두

존재할 수도

3.3 W-공간에서의 Point location 문제

먼저 외부

L과 6가 주어졌을 때, W|,

。가 접선에 대해서 같은 영영에 속하는지

판단하는 것은

그리 어렵지

그러나,

될지,

외접원이

바로 되는 것은 아니

그래서,

개가

지, 그리고 어떠한 접선이 외접원으로

될

판단할 필요가 있다.

여러 상황들을

경우로 구분할 수

Fig.

처럼 두

W과 W가 주어졌다고

하자. 여기서는

반지름은

Fig.

5. Configurations of circles in

and regions defined by two

tangent

and

한국CAD/CAM

논문집 제

저】

2001년 3월

점

집합의 보로노이

이용한 원

보로노이

계산

기하학적

니라고

and L는외부 접선이다.

+"

을 다음과 같이

4는

는 明과 必를 포함하는 반평면이라 하자.

반대쪽 반평면이다. 그리고

영역 모두

않는다. 그러면,

개의

영역으로 나누어진다.

a =（

£

，2）

Z

nZ，

） P

£i ciLj

Y = cL； 6 =

L|CZ，2

£=

（

（乙"乂2）

0 = （L,

CL?）

영

가 ot|

；

과

L；

로

다고

원점 0

_{과 Wz}

내부

（

（兎的

岭）

또

영역 丫는

개의 영역으로 구성되어

•평면의

외접원을

문제는 소위 point

문제로 축소된다.

그러면, 가능한

경우들이

같이 분류되어

참조）

Fig. 5

원점이

각의 경우가

6

점선으로

원은 내접원을

그려진

은 우리가 원하는

Fig. 6

제 너레이터

Z-평면에서

원이다. 검정색 점은

제너레이터 원을 나타낸다.

로 이러한 경우는 두

반지름이 작은 제너레이 터

동일하지 않을

•

가정호]■자. 그러면, 직선

은 Z-평면에서 6

W평면에서의

원이 서로 다른 영역에

때문에 두

를 내접하며,

점선으로 표시

였다. 이와는 반대로,

과

6

로 매핑되며, 그림에서는 실선으로

다.

＜

）가 이러한 경우이다.

두 접선은

서로

때

Z-평면에서도 尸에서 서로 교차한다.

•영역

：

두

"

과 W2

는 두

대서

서로 반대

놓이게

그렇기

외접원이

게 된다. Fig.

）가

경우를 나타낸다.

•영역 Y：

두

과 W2는 두

대해 원점과 같은

다. 그리하여

두

L

모두 외접원으로

Fig. 6.

VV-plane

핑하게

. 영역 5: 원점이 정확히

에 놓이게

변환은

평면에서와 비슷한

원점을 지나는 직선은

평면에서도

서로 접한

되기 때문이다. Fig.

（

）에 이 경우를

• 영역 e:

정확하게

£위에

그 직선은 Z-평면에서 직선으로 매핑되며,

지 한 직선은

원점과

원이

영역에

있기

내접원으로 매핑된다.

6

와 같은 결과가

•

：

8

정확히

점을 지나는 직선은 직선으로

되고

직선은 그

원점과 두 원이 같은

있기 때문에 외접원으로 매핑된다.

6（6

와 같은 결과가

그러나, Z-평면에서 제너레이터의

따라 위 의

된다. Fig. 5

b）

작은 반지름을

두 원의 반지름이 같을

Fig.

c）는 呼평면에서 두 원의 반지름이

한국

CAD/CAM

제 6

제

2001년

36 김동욱, 김덕수, 조동수,

Kokichi Sugihara

을

경우에 따라

존재하지

수도 있지만 위의 일반적인

와 같은 방식으로

예측할 수

이 논문에서는

설명은 생략하고 Fig.

에

앞에서

설명한

과

가

는 가정하에서의 예이다.

，!=¥L

그러나,

과 乙2가 동일한

발생한다. 세개의 주어진

이터

모두 동일하다면,

【終모두 점이

과 LA 동일한

되 는 것이다.

4.

모서리의 곡선식

꼭지점

즉 보로노이 꼭지점

산은

집합

다이어그램으로부터

보로노이

위상 정보를

중간에 발생한다.

원집합 보로노이 다이어 그램의 정확한 위상을 구했다면,

보로노이 모 서리의

수정해야 한다.

보로노이 모서리의 기하 정보는 두 제너레이터 사 이의 bisector인 것으로 알려져있다. 우리의 경우

는 직선이거나 쌍곡선의

두 제너레이터 원의 반지름이

우

쌍곡선 bisector- 두

반지름이 서 로 다를 경우 발생한다.

여러 종류의

존재한다. Persson 과

제시한 표현법과, 跖却皿이 제시한 표현법을 주목할 필요가

Persson과 Held는 모

식을 제너레이터의 옵셋 원소의 교차

풀어서 매개변수

표현하였다.

쌍곡선을 서로 다른

표현하

모서리의 식을 표현하는 데

예 외가 존재한다.

반대로,

은

Bezier

이 표현법은 CAD/CAM

의 종류가 예를 들어

쌍곡선, 포물선,

상관

하나의

형태로 표현할

그리하여,

옵셋팅邱같은 응용 을 단순화

수

그래서, 우리는

Bezier로

4.1 유리 2차Bezier로의 표현법

원

집합 보로노이

모서리는

직선이다. 그리고 원추 곡선은 아래에 정의

되어 있는 유리

곡선의 형태로

수

것도 알고

P1 _ fe [0> 1] (5)

bo, bb bz는 조정점이며, w0,

艸, 性는 각각의

정점에 대응되는 웨이트이다. 원추

포물선, 쌍곡선,

두 점

bz

곡선

있 고, 두

벡터가 그 점

나머지 하나의 곡

위의

경우 유리 이차

)로 변환

수

것은

알려져 있다

먼저 조정점들이 찾아졌다면,

조정점에 대응되 는

한다. 만약 구하고자 하는

선이 표준형이라 가정한다면, 즉, w

2=l.

wp은 다음과 같이

十质Ti

(6)

To-

좌표이다. 참고로 점

내 부에 있다고

더

내용 은 다음의 참고문헌에 잘 나와있다".

4.2 접선 벡터

우리의

보로노이 모서리의 두

끝에서의

의

하고

나머지 하나의

「

구하기 위해

끝

와

bisector의

벡터 가 필요하다. 이는 아래와 같이 쉽게 계산할 수

Fig. 7(a)

에서

인

과

)

가정하자.

과 P2 를

Fig.

7. Tangent vectors

(a) bisector

circles and

tangent

it, (b)

tangent

bisector at v.

한국

제

제

2001년

월

점

집합의 보로노이

보로노이

계산: II. 기하학적

L

은 V에서 각

을 이분한다고

7(b)

와

는

과 <3

부터

만큼 반지름이 축소된 원이라고 가정하자.

는

P

되며,

V-pjh 이다

Q

직선，위의

점이라고 하며,

이다. 그러

血-헤베Pi-

메이므 로 |q-Pd 비

』<

가 된다. 그러므로

q

곡선

놓일

직선

bisector 곡선의

에서의

이러한 이유로,

보로노이 꼭지점

에서의

2

선으로 쉽게 계산할 수 있다

또한

4인 경우는

되므로

구할 수 있다. 참고로

bisector도 꼭지점

에서 각을 이등분한다. 제너레이터가 점이 되더라도 이러한

예외의 경우가 되지 않는다.

이에

덧붙여, 이러한 관찰은

서로 교

이제 bisector곡선

위의 점을 어떻게 구하는가

는

하나 남아있다.

문제는 두 제너레이터 원의 중심점을 지나는

상의

제너레이터와

같은

점을 찾음으로써

해결할 수

다. 만일

의 내부에 존재한다면

으로 모서리의 식을 구할 수

이러한 경우

모서리는 삼각형의

놓이 게

그러나,

만일 곡선

점이

외

그러한

barycentric 좌표 勺은 음수가 되며

양수가

(6)에

음수가

유리

Bezier

형태로 구한 곡선은 우리가 원하는

놓이지

경우, 우리가 원하는 곡선 은 吐을 W|의

쉽 게 구할 수 있다也

5.실

험

원

집합 보로노이 다이어그램을

알고리 듬을 Intel

300

로 구현하고 실험하였다. 제시한 알고리 듬을

모듈로

점

보로노이 다이어그램 생성 모듈,

메인

집합의 보로노이

생성 모듈,

데이터 로드

저장 모듈,

메인

모듈은 다음의

모듈로 구성되어

모서리 플립

계산 모듈, iii)

(b)

Fig.

8. Examples

generators).

모서리의 기하정보 (즉,

bisector) 계산 모듈.

모서리

모듈에는

판단하고 플립 연산을 수행하는데,

앞의 논문

，

꼭지점의 위치를 계산하는 모듈과 보로노이 모서리의 기하 정보를 계산하는

듈은 본 논문의

Fig. 8은

집합

또 다른 예를 보여주고 있다. Fig. 8(a)

제너레이터

1,000개의 서로 교차하지

반지름을

는

Fig. 8(b)

경우는

상에 원들의

위치하고 서로 교차하지

름을

중심부에

지름을 가지는 제너레이터 원이 있는

Fig. 9는

8

대한 수 행 시간을 나타내었다. 수행시간은 VD(C)

VD(P) 모두 나타내었으며, 각각 동그란

정사각형 점 으로

참고로 표에서의 VD(C>

는 데 걸리는

VD(P)를

데

한국CAD/CAM학회 논문집

제 6

제 1

2001년

월

38 김동욱, 김덕수, 조동수,

Kokichi Sugihara

읟 ( 느 을

■•=

b)2 )

뜯

W

number

of

6000 4500 3000

0

2100 2800 3500 4200 number of generators

• VD(C) «VD(P)

Fig,

Computation

8.

시간을 뺀

시간이다. 그리고

계산하는 프로

본

한

Sugihara 홈 페이지에서의 코드를 사용하였다

VD(C)

와 VD(P)

계산 시간을 비교함에

를 계산하는

예상했던

많이

리지 않는다는 것을 추론할 수

표에서 R?

나 타나 있는

이는 통계학의 회

기법에서

최악의 경우

반해 실험상의

시간은 강력한

의 패턴을 보이는 것을

수 있다. 우리는

도 다른 많은 경우들을

보았는데,

경우

선형 패턴을 보이는 것으로 나타

실험을

제시한

매우 효율적이며 안정적이라고 말할 수

0(

최 악의

시나리오는 이론적으로는

매우 나타나기 어려운 경우라 판단

6

. 결 론

이 논문에서는

정 확한 꼭지점의 좌표와, 모서리의 기하 정보를 계산 하는 알고리듬을 제시하였다. 원들은 이차 유클리드

공간에 놓여 있고,

모두 동일할

요가

그리고

서로 교차하는 경우도 허 용한다. 제시한 알고리듬은 점 집합 보로노이

어그램의 위상으로부터

다이어그

올바른 위상을 얻는 앞의 논문에서 제시한

고리듬과

때 올바로

올바른 위상을

중간 과정에

원이 주어졌을 때,

꼭지점의 가능한 위치를 복소 평면에서의

변환을 통하여

분제는

제시한

계산 시간은 빠르

정확한 해를 구하며, 안정적이다.

정확한

위상과 꼭지점의

좌표가

보로노이

리

식은

였으며,

연산을 통해

우리는

선분과 원호가

폴리곤의 보로 노이 다이어그램을

있을 것이라

생각하고 있다. 그리고,

제시한

접근법과 비슷한 방법으로 평면에서의 폴리곤과,

보로노이 다이어그램을 구 하는 안정적인

확장할 수

것이라 기대하고 있다.

감사의 글

본

2000년도 "대학기초연구 지원사업''지원으로 수행되었으며

감사

또한 본 논문을

주신 심사 위 원님들께 감사

참고문헌

1. Boyer, C.

New York, 1968.

2.Courant,

R. and Robbins, H.,

An Elementary Approach to Ideas and Methods, 2nd edition, Oxford University Press, Oxford,

1996.

3.

Dome, H„

ematics: Their History and Solutions,

Dover,

York,

4. Drysdale,

Lee,

in

饷

Computing, pp.

833-842,

5.

R.

Vbronoi diagrams

searching,

Thesis,

한국CAD/CAM

제 1

2001

점 집합의

보로노이 다이어그램을 이용한 원

기하학적 측면

Computer

Tech.

­

University, 1979.

6.Fann, G., Curves and Surfacesfor Computer-Aided Geometric Design: A Practical Guide, 4thedition, Aca

­

Press,

1996.

7. Farin,

tical Use, 2nd edition, AK Peters,Natick, 1999.

8.

Fortune,

A Sweepline Algorithm

Voronoi

­

Vol. 2,

1987.

9.

Hamann, B.

A tessellation

representation

NURBS surfaces

arbitrary trimming

Vol.

28,

No. (6/7),

461-472, 1996.

10. Held,

Computational

of

Machining, LNCS, Springer-Verlag, 1991.

11.

Held,

Lukacs, G.

L.,

H-Parallel

Paths

Means

Proximity

Vol.

No. 3,

189-203, 1994.

12.Johnson,

R. A.,

tise on the Geometry of the Triangle and the Circle,

Houghton

Boston, 1929.

13. Kim,

I.-K. and

B.-J., Representing

Voronoi diagram of

polygon using

curves,

27,

No. 8, pp.

1995.

14. Kim, D.S, Polygon

Voronoi

two

Vol.

No.

14, pp. 1069-1076,

1998.

15.

Kim,

Lee, S.-W. and Shin, H.,

cocktail

­

planar

Vol. 30,

13,

1998.

16.

김덕수,

, 조영송,

Bezier

호도그래프”

한국

학회 논문집, 저】3

2호, pp.

1998.

17.

조동수,

K-,

집합의

로노이 다이어그램과

집합의

다이어그램

관계

(submitted

CAD/

CAM학회 논문집).

18.Kreyszig, E.,Advanced Engineering Mathematics, Th Edition, John Wiley

& Sons, 1993.

19.

D.

and

R. L., Generalization

Vbronoi diagrams

10, No. 1, pp. 73-87, 1981.

20.

C

n- puter Science Press,

1988.

21.

Okabe,

Boots,

­ sellations Concepts

of Vbronoi

­

J아in

& Sons,

22.

Persson,

NC

of

shaped pock­

ets,

Vol. 10, No.

169- 174, 1978.

23.

F. P,

Shamos, M.

Springer-Verlag,

York,

1985.

24.

Sharir,

for

set

V

14, No.

2, pp.

1985.

25.Sugihara,

K., Approximation

generalized Vbronoi

­

Vbronoi

Vbl. 55, No. 6, pp.

26. Sugihara, K.,

)

. 김 동 욱

1999년 한양대학교 산업공학과 학사 2001년 한양대학교 산업공학과 석사 2001년-현재 한양대학교 산업공학과 박사과정 관심분야: computational geometry, com­

puter graphics

김 덕 수

1982년 한양대학교 산업공학과 학사 1985년 New Jersey Institute of Technology

산업공학과 석사

1990년 The University of Michigan 산업 공학과 박사

198见~1991년 Schlumberger Ifechnology CAD/CAM Co. Senior Software Engineer

1991 년~1995년 삼성 종합 기술원 선임 연 구원

1995년~현재 한양대학교 산업공학과 부교수 심'분4야: geometric modeling, computa­

tional geometry, STEP and Internet applications

조 동 수

1985년 한양대학교 산업공학과 학사 1992년 한양대학교 산업공학과 석사 1997년~현재 한양대학교 산업공학과 박사과

정（국제 신경명 컨설팅 실장）

1984-1992 기아자동차에서 근무 관심분야:

Kokichi Sugihara

1971년 동경대학교 계수공학과 학사 1973년 동경대학교 계수공학과 석사 1980년 동경대학교 계수공학과 박사 1991년~현재 동경대학교 대학원 계수공학과

교수 관심분야:

한국CAD/CAM

논문집 제

권 제

2001년