رویکردی جدید برای شمارش یا بهینه سازی مثلث بندی مجموعه نقاط در صفحه مبتنی بر MIS
محورهای موضوعی : مهندسی برق و کامپیوتر
1 - دانشگاه تربیت دبیرشهید رجایی
2 - دانشگاه تربیت دبیرشهید رجایی تهران
کلید واژه: مثلث‌بندیمثلث‌بندی با کمترین وزنمسئله شمارشمجموعه مستقل بیشینگراف تقاطع,
چکیده مقاله :
مثلث‌بندی مجموعه نقاط S در صفحه، برابر با تعبیه مسطح یک گراف مسطح مستقیم‌الخط بیشین (با بیشترین یال) روی مجموعه نقاط است به طوری که مجموعه رئوس گراف دقیقاً همان مجموعه نقاط داده شده باشد. دو مسئله مهم در این زمینه مورد تحقیق است. الف) به چند طریق می‌توان مجموعه نقاط S را مثلث‌بندی کرد ب) کدام مثلث‌بندی بر اساس ویژگی خاصی بهینه است. مسئله اول یک مسئله باز است و به جز در شرایط خاص که دارای رابطه بسته می‌باشد تا به حال الگوریتمی با زمان چندجمله‌ای برای آن در حالت کلی ارائه نشده است. مسئله دوم نیز در حالتی که هدف پیداکردن مثلث‌بندی که مجموع طول یال‌های آن کمترین باشد یک مسئله NP-HARD است (MWT)، لذا تحقیقات در راستای ارائه الگوریتم‌های مکاشفه‌ای، فرامکاشفه‌ای یا تقریبی برای این دو حالت انجام شده است. در این مقاله روشی ارائه شده که در آن با تولید گراف تقاطع حاصل از تمامی پاره‌خط‌های حاصل از تمامی زوج نقاط S تولید می‌شود و سپس الگوریتم‌هایی برای تولید همه مجموعه‌های مستقل بیشین (MIS) گراف تقاطع و همچنین روشی برای شمارش تعداد این مجموعه‌ها ارائه می‌شود. این رویکرد تولید گراف تقاطع و تبدیل مسئله مثلث‌بندی به مسئله مجموعه مستقل بیشین نگاهی جدید به مسئله مثلث‌بندی در هر دو حالت الف و ب محسوب می‌شود و از آنجا که ارائه الگوریتم برای مسئله الف یا ب به خاطر ذات هندسی‌بودن آن دشوار است لذا با رویکرد مطرح‌شده در این مقاله، تمامی الگوریتم‌هایی که تا به حال برای مسئله MIS مطرح شده است را می‌توان برای حل مسئله مثلث‌بندی در هر دو حالت الف یا ب به کار برد. تکنیک تبدیل مسئله مثلث‌بندی به مسئله MIS رویکردی است که تا به حال روشی مبتنی بر آن برای حل مسایل شمارش تعداد طرق مثلث‌بندی یا مثلث‌بندی با کمترین وزن گزارش نشده است. علاوه بر این یک روش تخمینی مکاشفه‌ای برای تعیین متوسط تعداد حالات مثلث‌بندی ارائه خواهد شد که نتایج پیاده‌سازی نشان می‌دهد روی نمونه‌هایی از ورودی نزدیک به مقدار دقیق هستند.
The triangulation of the given point set on the 2D-plane is the planar straight-line embedding of the graph whose vertices is exactly and set of its edges is maximal (with the most edge). Two important issues are being explored in this area. a) In how many ways can the given set of points be triangulated? b) Which triangulation is optimal based on the given particular feature? The first problem is an open problem, and except in special cases where it has a closed relation, a polynomial time algorithm for it has not been presented in general. The second problem is NP-HARD when the goal is to find a triangulation whose total edge length is the smallest (MWT). So research has been done to provide heuristic, meta heuristic, or approximation algorithms for it. In this paper, a method is presented in which by constructing the intersection graph obtained from all the line segments obtained from all pairs of points of and then algorithms for generating all maximal independent sets (MIS) of the intersection graph is introduced. Furthermore, an algorithm is introduced for counting the number of maximal independent sets. This approach in which constructing intersection graph and converting any triangulation problem to the maximal independent set problem is a new approach for triangulation problem in both cases (a) and (b). Considering difficulties to design algorithms for problems (a) and (b) because of its geometric natures, all the algorithms that have been proposed so far for problems (a) and (b) can be used to solve the triangulation problems in both cases by the approach proposed in this article. The proposed approach of converting triangulation problem to the MIS problem is a new approach that has never been reported to solve counting the number of triangulations or minimum weight triangulation. Furthermore a heuristic estimation algorithm will be introduced to estimate average number of triangulations on the given point set and the algorithm implementation shows its outputs is near to exact values for some instances.
[1] L. P. Chew, "Constrained delaunay triangulations," Algorithmica, vol. 4, no. 1, pp. 97-108,. 1986.
[2] D. Shojaee, H. Helali, and A. A. Alesheikh, "Triangulation for surface modeling," in Proc. 9th Symp. on 3D Analysis of Human Movement, poster session, Valenciennes, France, 28-30 Jun. 2006.
[3] R. D. Duppe and H. H. Gottschalk, "Automatische interpolation von isolinien bei willkürlichen stützpunkten," Allgemeine Vermessungsnachrichten, vol. 77, no. 10, pp. 423-426, 1970.
[4] M. I. Shamos and D. Hoey, "Closest-point problems," in Proc. 16th IEEE Annual Symp. On Foundations of Computer Science, pp. 151-162, USA, 13-15 Oct. 1975.
[5] E. L. Lloyd, "On triangulations of a set of points in the plane," in Proc. 18th IEEE Annual Symp. on Foundations of Computer Science, pp. 228-240, Providence, RI, USA, 31 Oct.-2 Nov. 1977.
[6] D. G. Kirkpatrick, "A note on delaunay and optimal triangulations," Information Processing Letters, vol. 10, no. 3, pp. 127-128, Apr. 1980. [7] M. R. Garey, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1978.
[8] W. Mulzer and G. Rote, "Minimum-weight triangulation is NP-hard," J. of the ACM, vol. 55, no. 2, pp. 1-29, 2008.
[9] J. Remy and A. Steger, "A quasi-polynomial time approximation scheme for minimum weight triangulation," J. of the ACM, vol. 56, no. 3, Article No.: 15, May 2009.
[10] M. Jahani, B. Sadeghi Bigham, and A. Askari, "An ant colony algorithm for the minimum weight triangulation," in Proc. IEEE Int. Conf. on Computational Science and Its Applications, vol. 1, pp. 81-85, Fukuoka, Japan, 23-26 Mar. 2010.
[11] E. L. Lawler, "A note on the complexity of the chromatic number problem," Inf. Proc. Lett., vol. 5, pp. 66-67, 1976.
[12] J. W. Moon and L. Moser, "On cliques in graphs," Israel J. of Mathematics, vol. 3, no. 1, pp. 23-28, 1965.
[13] M. Luby, "A simple parallel algorithm for the maximal independent set problem," SIAM J. on Computing, vol. 15, no. 4, pp. 1036-1053, Nov. 1986.
[14] P. Erdos, A. W. Goodman, and L. Posa, "The representation of a graph by set intersections," Canadian J. of Mathematics, vol. 18, pp. 106-112, 1966.
[15] E. S. Marczewski, "Sur deux propriétés des classes d'ensembles," Fund. Math, vol. 33, pp. 303-307, 1945. (in French)
[16] M. D. Plummer, "Some covering concepts in graphs," J. of Combinatorial Theory, vol. 8, no. 1, pp. 91-98, Jan. 1970.