چهارشنبه، ۳ خرداد ۱۳۹۶   


دانشگاه تحصیلات تکمیلی علوم پایه زنجان

بلوار استاد یوسف ثبوتی، پلاک 444

صندوق پستی 1159-45195 زنجان 66731-45137 ایران

دورنگار: 33155142 -024

تلفن: 33151 -024


طراحی و برنامه نويسی توسط مركز كامپيوتر دانشگاه تحصيلات تكميلي علوم پايه زنجان

خانه>دانشکده علوم رایانه و فناوری اطلاعات>
دانشکده علوم رایانه و فناوری اطلاعات
 
 
1- Keikhah, V., Mohades, A., Davoodi Monfared, M., "On the Triangulation of non-fat Imprecise Points ", Proceedings of the 28th Canadian Conference on Computational Geometry August 3-5, 2016 Simon Fraser University Vancouver, British Columbia Canada, 114-121, (624).

Abstract:
In this paper, we address the problem of computing a triangulation of imprecise points modeled by non-fat regions posed by Van Kreveld et al. [SIAM J. Com-put(39), 2990-3000 (2010)]. In particular, we study the problem of preprocessing a set of n line segments in the plane so that if one point per region is specified with precise coordinates, a triangulation of the points can be computed in o(nlog n) time. We first model the points with perpendicular line segments and show if imprecise points have uniform distribution in their corresponding bounding box, in O (nlog n) preprocessing time a trian- gulation of any exact set of points can be computed in expected linear time. Although, we show even comput- ing an arbitrary triangulation in this model can take Ω(nlog n) time in the worst case. Also some related lower bound proofs are provided at the end