TAILIEUCHUNG - Effective Computational Geometry for Curves & Surfaces - Boissonnat & Teillaud Part 5

Tham khảo tài liệu 'effective computational geometry for curves & surfaces - boissonnat & teillaud part 5', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 90 J-D. Boissonnat C. Wormser M. Yvinec Algorithm 2 Construction of Apollonius diagrams Input a set of hyperspheres s 1. Compute Si for i 1 . n 2. Compute the power diagram of the Si s 3. For all i 1 . n project vertically the intersection of the power region L Si with the half-cone Ci. Output the Apollonius diagram of s. The Apollonius diagram of 5 can be computed using the following algorithm The power diagram of the Si can be computed in time O nL2 J 1 log n . The intersection involved in Step 3 can be computed in time proportional to the number of faces of the power diagram of the Si s which is O nL2 J 1 . We have thus proved the following theorem due to Aurenhammer 35 Theorem 10. The Apollonius diagram of a set of n hyperspheres in Rd has complexity O nL2J 1 and can be computed in time O nL2J 1 logn . This result is optimal in odd dimensions since the bounds above coincide with the corresponding bounds for the Voronoi diagram of points under the Euclidean distance. It is not optimal in dimension 2 see Exercise 20 . We also conjecture that it is not optimal in any even dimension. Computing a Single Apollonius Region We now establish a correspondence due to Boissonnat and Karavelas 63 between a single Apollonius region and a Mobius diagram on a hypersphere. To give the intuition behind the result we consider first the case where one of the hyperspheres say ƠQ is a hyperplane . a hypersphere of infinite radius. We take for ƠQ the hyperplane xd 0 and assume that all the other hyperspheres lie the half-space xd 0. The distance ỗQ x from a point x G Rd to ƠQ is defined as the Euclidean distance. The points that are at equal distance from ƠQ and Ơi i 0 belong to a paraboloid of revolution with vertical axis. Consider such a paraboloid as the graph of a d 1 -variate function Ai defined over Rd 1. If follows from Sect. that the minimization diagram of the ớj i 1 . n is a Mobius diagram see Fig. . Easy computations give the associated weighted points. Write

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.