http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : van Kreveld, M. (검색결과 1 건)
- 무료
- 기관 내 무료
- 유료
-
Empty pseudo-triangles in point sets
Ahn, H.K.,Bae, S.W.,van Kreveld, M.,Reinbacher, I.,Speckmann, B. North Holland ; Elsevier Science Ltd 2011 Discrete applied mathematics Vol.159 No.18
We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Θ(n<SUP>2</SUP>) and Θ(n<SUP>3</SUP>) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n<SUP>3</SUP>) and Θ(n<SUP>6</SUP>). If we count only star-shaped pseudo-triangles, the bounds are Θ(n<SUP>2</SUP>) and Θ(n<SUP>5</SUP>). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n<SUP>3</SUP>) time. In the general case, the running times are O(n<SUP>6</SUP>) for the maximization problems and O(nlogn) for the minimization problems.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
