برای اطلاع از آخرین مقالات علمی و اخبار کرونا(COVID-19) کلیک کنید

مشخصات مقاله

عنوان: 

الگوريتم جديد براي مساله تعيين وضعيت نقطه در چند ضلعي محدب

نوع ارائه: پوستر
نویسنده: ابوالحسني سيدمحمد,رزازي محمدرضا
 
 
 
عنوان همایش: كنفرانس ملي سالانه انجمن كامپيوتر ايران
نوع همایش:  انجمن هاي علمي
حامی:  انجمن کامپیوتر ایران، دانشگاه صنعتی شریف
زمان:  1386دوره 13
 
 
چکیده: 

تعيين وضعيت نقطه نسبت به يک چند ضلعي يکي از مسائل بنيادي هندسه محاسباتي است. در اين مقاله، الگوريتمي جديد به منظور تعيين وضعيت يک نقطه نسبت به يک چندضلعي محدب ارائه مي شود. الگوريتم هاي قبلي ارائه شده براي تعيين وضعيت نقطه نسبت به چندضلعي محدب يک پيش پردازش بر روي راس هاي چندضلعي انجام مي دهند و سپس وضعيت نقاط مورد بررسي را مورد ارزيابي قرار مي دهند. در الگوريتم پيشنهادي نيازي به پيش پردازش نيست. در اين الگوريتم با استفاده از جستجوي باينري بين راس هاي چندضلعي، سه راسي پيدا مي شوند که نقطه مورد جستجو در داخل مثلث ايجاد شده از اين سه راس باشد. در صورتي که چنين مثلثي پيدا شد نقطه داخل چندضلعي قرار دارد و در غير اين صورت نقطه در خارج مثلث قرار دارد. اين الگوريتم در شرايطي که توزيع نقاط به صورت يکنواخت باشد وضعيت نقطه را در زمان ثابت ((1)O) مشخص مي کند. هر چند که پيچيدگي زمان الگوريتم در بدترين حالتO(log n)  است.

 
کلید واژه: هندسه محاسباتي، دربرداري چندضلعي محدب، روش هاي بر اساس مثلث
 
مقالات نشریه ای مرتبط: 
 
مقالات همایشی مرتبط: 
 
 
بازدید یکساله 201   pdf-file
 
آخرین های بلاگ
ورود به بلاگ مرکز اطلاعات علمی