मैं डी बर्ग, एट अल द्वारा कम्प्यूटेशनल ज्यामिति पुस्तक से दृश्यता ग्राफ एल्गोरिदम लागू करने की कोशिश कर रहा हूं। आप यहां एल्गोरिदम पा सकते हैं: http://cs.smith.edu/~streinu/Teaching/Courses/274/Spring98/Projects/Philip/fp/algVisibility.htm
मुझे विस्मयकारी एल्गोरिदम की पहली पंक्ति में परेशानी हो रही है:
if pwi intersects the interior of the obstacle of which wi is a vertex, locally at wi then return false
पुस्तक में कहा गया है कि इसे ओ (एलजी एन) समय लेना चाहिए(जहां विमान विमान में सभी बिंदु हैं), लेकिन यह जांच नहीं करता है कि चेक कैसे करें। मैंने पाया है कि एल्गोरिदम बहुभुज के शिखर की संख्या के संबंध में रैखिक समय लेते हैं।
किसी भी मदद की सराहना की है।
उत्तर:
जवाब के लिए 0 № 1मेरा मानना है कि जिस चरण के साथ आप चिंतित हैं, वह ज्यादातर ओ (लॉग n) पहर, क्योंकि आप बाधा पर बाइनरी खोज का उपयोग कर सकते हैं जिसके लिए wमैं एक कट्टरपंथी है