ปัญหาการมองเห็นบนภูมิประเทศ

Visibility problems on terrains

Name: ชวิน เอี่ยมวรวุฒิกุล

ThaSH: มหาวิทยาลัยเกษตรศาสตร์ -- วิทยานิพนธ์. วศ.ม. (วิศวกรรมคอมพิวเตอร์) 2563.

Classification :.LCCS: QA76.9.C58

ThaSH: มหาวิทยาลัยเกษตรศาสตร์. -- สาขาวิศวกรรมคอมพิวเตอร์ -- วิทยานิพนธ์

ThaSH: กริด (ระบบคอมพิวเตอร์)

ThaSH: แบบจำลองทางภูมิศาสตร์

Abstract: ในการสร้างสถานีเพื่อติดต่อสื่อสารกันบนภูมิประเทศนั้นจะมีค่าใช้จ่ายที่แตกต่างกันและให้การส่งสัญญาณระหว่างสถานีแทนการมองเห็นกันระหว่างสถานี ดังนั้นเราพิจารณาปัญหาการมองเห็นบนภูมิประเทศโดยให้สถานีส่งสัญญาณตั้งอยู่ที่ตำแหน่งที่แตกต่างกันบนภูมิประเทศ ต้องการหาความสูงของหอคอยที่เหมาะสมในการส่งสัญญาณสามารถสื่อสารกันได้อย่างอิสระและมีค่าใช้จ่ายต่ำที่สุด ซึ่งเราจะนิยามปัญหาได้ดังนี้ ให้จุดสองจุด q1 และ q2 อยู่บนภูมิประเทศ ต้องการหาความสูง h1 และ h2 ที่เมื่อยกจุด qi ขึ้นด้วยความสูง hi , สำหรับ i= 1,2 จุดที่ยกขึ้นจะสามารถมองเห็นกันและกันได้โดยมีค่าใช้จ่ายที่ขึ้นอยู่กับความสูง h1 และ h2 เป็นเชิงเส้น ปัญหาที่เราสนใจแบ่งเป็นสองปัญหา ปัญหาแรกเมื่อให้จุด q1 และ q2 บนภูมิประเทศที่มีจุดยอด n จุด เราสามารถประมวลผลล่วงหน้าโดยใช้เวลาในการทำงานเป็น O(n logn) และสามารถตอบคำถามได้ในเวลา O(log n+d) โดยที่ d คือจำนวนของเส้นเชื่อมของภูมิประเทศระหว่าง q1 และ q2 ปัญหาต่อมาเมื่อให้จุด q1 คงที่ให้จุด q2 และ ε > 0 เราสามารถหาคำตอบที่มีความผิดพลาดไม่เกิน ε ได้ในเวลา O(log2 (hmax/ε) • logn) โดยที่ hmax คือความสูงของจุดที่สูงที่สุดบนภูมิประเทศในปัญหานี้การประมวลผลล่วงหน้าใช้เวลาในการทำงานเป็น Õ(n 2 ). We consider visibility problems on a terrain. Given two stations located at different points on the terrain, we would like to find the minimum heights of communication towers at the two locations so that they can communicate freely. Formally, given two points q1 and q2 on the terrain, we would like to find the heights h1 and h2 such that if one lift qi up by hi , for i = 1,2, the lifted points see each other with the minimum cost that depends linearly on h1 and h2 . We consider two versions of the problem. When given two points q1 and q2 on terrain with n vertices, with the preprocessing time of O(n log n), we can answer the query in time O(log n+ d) where d is the number of terrain edges between q1 and q2 . When one point q1 is fixed, given q2 and ε > 0, we can give an approximate answer with an additive error at most ε in time O(log2 (hmax/ε) · log n) where hmax is the maximum height in terrain. In this case, the preprocessing time is Õ(n 2 ).

มหาวิทยาลัยเกษตรศาสตร์. สำนักหอสมุด

Address: กรุงเทพมหานคร

Email: tdckulib@ku.ac.th

Name: จิตร์ทัศน์ ฝักเจริญผล

Role: อาจารย์ที่ปรึกษาวิทยานิพนธ์หลัก

Name: ภารุจ รัตนวรพันธุ์

Role: อาจารย์ที่ปรึกษาวิทยานิพนธ์ร่วม

Created: 2563

Modified: 2568-07-11

Issued: 2568-07-11

วิทยานิพนธ์/Thesis

วิทยานิพนธ์/Thesis

application/pdf

URL: https://www.lib.ku.ac.th/KUthesis/2563/chawin-aie-all.pdf

CallNumber: QA76.9.C58 .ช17

tha

DegreeName: วิศวกรรมศาสตรมหาบัณฑิต

Level: ปริญญาโท

Descipline: วิศวกรรมคอมพิวเตอร์

Grantor: มหาวิทยาลัยเกษตรศาสตร์

©copyrights มหาวิทยาลัยเกษตรศาสตร์

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	chawin-aie-all.pdf	1.22 MB

ใช้เวลา

0.034021 วินาที