http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : Reinbacher, I. (검색결과 4 건)
- 무료
- 기관 내 무료
- 유료
-
Maximum overlap of convex polytopes under translation
Ahn, H.K.,Cheng, S.W.,Reinbacher, I. Elsevier 2013 Computational Geometry Vol.46 No.5
We study the problem of maximizing the overlap of two convex polytopes under translation in R<SUP>d</SUP> for some constant d≥3. Let n be the number of bounding hyperplanes of the polytopes. We present an algorithm that, for any ε>0, finds an overlap at least the optimum minus ε and reports the translation realizing it. The running time is O(n<SUP>@?d/2@?+1</SUP>log<SUP>d</SUP>n) with probability at least 1-n<SUP>-O(1)</SUP>, which can be improved to O(nlog<SUP>3.5</SUP>n) in R<SUP>3</SUP>. The time complexity analysis depends on a bounded incidence condition that we enforce with probability one by randomly perturbing the input polytopes. The perturbation causes an additive error ε, which can be made arbitrarily small by decreasing the perturbation magnitude. Our algorithm in fact computes the maximum overlap of the perturbed polytopes. The running time bounds, the probability bound, and the big-O constants in these bounds are independent of ε.
-
배상원(Sang Won Bae),Iris Reinbacher,안희갑(Hee-Kap Ahn) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.1
본 논문에서는 평면상에 n개의 점집합과 세 꼭지점이 주어졌을 때, 내부에 점을 포함하지 않는 최단 둘레의 유사삼각형을 구하는 문제를 다룬다. 이때, 입력으로 주어진 세 꼭지점은 유사삼각형의 볼록꼭지점이 되며, 둘레의 길이는 유사삼각형을 구성하는 선분들의 길이의 합으로 측정한다. 본 논문은 이러한 최적의 유사삼각형을 선형공간을 사용하여 O(n³) 시간에 계산하는 알고리즘을 제시한다. 이와 함께, 이와 유사한 최적화 문제들로 내부 면적을 최대화하는 유사삼각형과 가장 긴 오목체인을 최소화하는 유사삼각형 문제들을 고려하며, 선형공간을 사용하여 각각 O(n³)과 O(n²log n) 시간에 최적 유사삼각형을 계산하는 알고리즘을 제시한다.
-
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.
-
Covering points by disjoint boxes with outliers
Ahn, H.K.,Bae, S.W.,Demaine, E.D.,Demaine, M.L.,Kim, S.S.,Korman, M.,Reinbacher, I.,Son, W. Elsevier 2011 Computational Geometry Vol.44 No.3
For a set of n points in the plane, we consider the axis-aligned (p,k)-Box Covering problem: Find p axis-aligned, pairwise-disjoint boxes that together contain at least n-k points. In this paper, we consider the boxes to be either squares or rectangles, and we want to minimize the area of the largest box. For general p we show that the problem is NP-hard for both squares and rectangles. For a small, fixed number p, we give algorithms that find the solution in the following running times: For squares we have O(n+klogk) time for p=1, and O(nlogn+k<SUP>p</SUP>log<SUP>p</SUP>k) time for p=2,3. For rectangles we get O(n+k<SUP>3</SUP>) for p=1 and O(nlogn+k<SUP>2+p</SUP>log<SUP>p-1</SUP>k) time for p=2,3. In all cases, our algorithms use O(n) space.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
