عنوان
توليد چندضلعي‌هاي ساده متعامد تصادفي به روش ضربه‌اي
نویسنده (گان)
نوراله,علي;مهران فر,کامران
چکیده مقاله
توليد چندضلعي‌هاي تصادفي از مسائل مهم هندسه محاسباتي است که در تحقيقات روان‌شناختي، گرافيک کامپيوتري و از همه مهمتر براي بررسي درستي الگوريتمها به کار مي‌رود. نوع خاصي از چندضلعيهاي تصادفي، چندضلعيهاي متعامد ميباشند که در آنها هر دوضلع مجاور بر هم عمود مي‌باشند و اضلاع پشت سر هم به صورت متناوب افقي و عمودي هستند. در اين مقاله ابتدا مفهوم جديدي به نام ضربه تعريف مي گردد و سپس الگوريتمي از مرتبه o(hn) و با استفاده از تکنيک ضربه اي ارائه مي شود که در آن h تعداد ضربات و n تعداد اضلاع چندضلعي است، يعني ورودي مسئله يک چندضلعي ساده مربع يا مستطيل شکل، در قالب چهار نقطه در فضاي دوبعدي و نيز تعداد ضربات وارده به اين چندضلعي توسط يک چکش مجازي است و خروجي مسئله يک چندضلعي ساده متعامد تصادفي مي‌باشد. اين الگوريتم روشي جديد در توليد چندضلعي محسوب مي شود و مي تواند مبناي کار روشهاي ديگري محسوب شود.

متن کامل مقاله