Pick's Theorem


উপরের চিত্রের মতো বিদঘুটে কোন বহুভুজের ক্ষেত্রফল বের করতে ব্যাবহৃত হয় পিক'স থিওরি!

যদি বহুভুজটির ভার্টেক্স বা কৌণিক বিন্ধুসমূহ গ্রাফ পেপারের ইন্টিজার পয়েন্টগুলো হয় তবে বহুভুজটির ক্ষেত্রফল হবেঃ

Area = i + (b/2) - 1 = (2*i + b - 2)/2

এখানে,     i - Number of points inside the polygon
                b - Number of points on the boundary of the polygon

এখন, পিক'স থিওরি টা আসলে যেভাবে আসছেঃ

১) আমি যদি গ্রাফ পেপারে লম্বভাবে অবস্থিত অথবা অনুভুমিকভাবে অবস্থিত ২ টি বিন্দুর মধ্যবর্তী দূরত্ব এক একক ধরি তবে গ্রাফ পেপারে অংকিত ক্ষুদ্রতম ত্রিভূজের ক্ষেত্রফল হবে ১/২। 
(এখানে, ক্ষুদ্রতম ত্রিভুজ বলতে বুঝানো হয়েছে এমন একটা ত্রিভুজ যার কৌণিক বিন্ধুগুলো গ্রাফ পেপারের ইন্টিজার পয়েন্ট হবে কিন্তু ত্রিভুজের অভ্যন্তরে কোন ইন্টিজার পয়েন্ট থাকবে না।অর্থাৎ, যার b=3 , i=0)। এমন সকল ত্রিভুজের ক্ষেত্রফল ই ১/২ হবে শতভাগ নিশ্চিত।

২) এবার আমি বহুভুজটিকে ক্ষুদ্রতম ত্রিভুজে স্প্লিট করবো।

৩) তাহলে, বহুভুজটির ক্ষেত্রফল বের করতে পারবো যদি আমি তাকে কতটি ক্ষুদ্রতম ত্রিভুজে স্প্লিট করা যায় সেটা জানি। তার মানে, আমার এখন মূল মাথাব্যাথা হচ্ছে ত্রিভুজ এর সংখ্যা বের করা!!!

এখন, আমরা যদি আমাদের বহুভুজটিকে একটি Planar Graph এ রুপান্তর করতে পারি(যেখানে বহুভুজটি অনেকগুলো ক্ষুদ্রতম ত্রিভুজে স্প্লিট হবে) তবে Euler Characteristics of a Planar Graph
ব্যাবহার করে ত্রিভুজের সংখ্যা বের করা সম্ভব।



এখন আমাদের Planar Graph টি তে যদি f সংখ্যক faces থাকে তবে ত্রিভুজের সংখ্যা = f-1

এখন, Planar Graph এর আরেকটি প্রোপার্টি হচ্ছে,
 
3*(f-1) + edges on boundary = 2*Total edges

উপরের গ্রাফের জন্য, 3*13 + 7 = 2*23 = 46

প্রোপার্টিটিকে যদি লিখি,

          3*(f-1) + eb = 2*eT
=>    f = 2*(eT - f) - eb + 3
=>    f = 2*(v-2) - eb + 3       ; For Planar Graph, 2 = v - eT + f
=>    f = 2*(i+b-2) - b +3      ;  v = i+b & eb = b
=>    f-1 = 2*i + b - 2
=>    Number of Triangles = 2*i+b-2

So, Area = (2*i + b - 2)/2

পিক'স থিওরি বুঝে থাকলে এই প্রব্লেম টি চেষ্টা করে দেখতে পারো।

Happy Coding-_-

Comments

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

Magic In Grid

At Coder Educational DP-B | DP Series(Episode-2)