جداسازی نقاط دو رنگ با دو- گوه با زاویه مشخص
محورهای موضوعی : electrical and computer engineeringمریم ملکی شهرکی 1 , علیرضا باقری 2 , مهدیس نیری 3
1 - دانشگاه آزاد اسلامی واحد تهران شمال
2 - دانشگاه صنعتی امیرکبیر
3 - دانشگاه آزاد اسلامی واحد تهران شمال
کلید واژه: هندسه محاسباتي پوشش جداسازي دو- گوه الگوريتم نقاط دو رنگ,
چکیده مقاله :
مسئله پوشش از مسایل مهم و پرکاربرد در هندسه محاسباتي است که در اين مسأله، نقاط بايستي با حداقل يک شکل هندسي پوشانده شوند. نوع خاصي از مسأله پوشش، مسئله جداسازي نقاط است که در اين مسئله حداقل دو دسته نقطه وجود دارد که تمايز آنها با رنگ نشان داده مي‌شود (براي مثال نقاط آبي و قرمز) و بايستي نقاط با يک شکل هندسي از هم جدا شوند که به اين شکل هندسي، جدا‌کننده مي‌گويند. در اين مقاله مسئله جداسازي نقاط آبي و قرمز با دو- گوه جدا‌کننده با زاويه مشخص مورد بررسي قرار مي‌گيرد. الگوريتم ارائه‌شده براي اين مسأله تمام دو- گوه‌هاي جدا‌کننده با زاويه مشخص را در زمان بهينه O (n log n) گزارش مي‌کند.
The point-set covering is one of the important problems in computational geometry, which has many applications. In this problem, the given points should be covered by at least one geometric shape. A variant of the problem is the point-set separation, in which there are at least two different kinds of points which are colored by different colors. The geometric shapes, which are called separators, should only cover the points of the same color. In this paper, separation of blue and red points by a double-wedge of a given angle θ is considered. The proposed algorithm reports all separator θ angle double-wedges in optimal time O(nlogn).