Chulalongkorn University Theses and Dissertations (Chula ETD)
Two-finger caging of concave polygon
Other Title (Parallel Title in Other Language of ETD)
การกักขังรูปหลายเหลี่ยมเว้าด้วยสองนื้ว
Year (A.D.)
2005
Document Type
Thesis
First Advisor
Attawith Sudsang
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Degree Name
Master of Engineering
Degree Level
Master's Degree
Degree Discipline
Computer Engineering
DOI
10.58837/CHULA.THE.2005.1584
Abstract
An object is captured by a set of fingers when there exists no trajectory to bring the object arbitrarily far from the fingers. Object concavity is a special geometric property that allows objects to be captured with only few fingers. In particular, certain concave objects can be captured by appropriately placing two fingers close to some pair of opposite concave sections. This work addresses the problem of computing all configurations of the two fingers that capable of capturing the object. Those configurations will be represented in such a way that answering whether a finger configuration can capture the object requires O(lgn) running time in most cases (where n is the number of vertices of the object.) In computing all configurations capable of capturing the object, we proposed a O(n[superscript2]lgn) algorithm
Other Abstract (Other language abstract of ETD)
วัตถุที่ถูกกักขังนั้นจะไม่มีทางที่จะเล็ดรอดออกจากนิ้วหุ่นยนต์ ได้ (ซึ่งเปรียบเสมือนซี่กรงขัง) การที่วัตถุไม่สามารถเล็ดรอดออกไปได้นั้นคือการที่ไม่สามารถเคลื่อนย้ายวัตถุไปให้ไกลแสนไกลจากนิ้วต่างๆ ได้ คุณสมบัติความเว้าของวัตถุเป็นคุณสมบัติเชิงเรขาคณิตที่ช่วยให้การกักขังวัตถุทำได้แม้ใช้เพียงไม่กี่นิ้ว ในเชิงลึกนั้นการที่จะกักขังวัตถุที่มีความเว้าบางชนิดสามารถทำได้โดยใช้นิ้วเพียงสองนิ้ว งานวิทยานิพนธ์นี้มุ่งเน้นที่จะศึกษาปัญหาการคำนวณหารูปแบบการวางนิ้วสองนิ้วทั้งหมดที่สามารถกักขังวัตถุได้ โดยการบรรยายรูปแบบการวางนิ้วทั้งหมดดังกล่าวสามารถนำไปใช้ในการตรวจสอบว่ารูปแบบการวางนิ้วที่ต้องการตรวจสอบนั้นสามารถกักขังวัตถุได้หรือไม่ได้ในเวลา O(lgn) สำหรับในกรณีทั่วๆ ไปในการคำนวณเพื่อบรรยายรูปแบบการวางนิ้วทั้งหมดดังกล่าวนั้น สามารถทำได้ในเวลา O(n[superscript2]lgn).
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Pipattanasomporn, Peam, "Two-finger caging of concave polygon" (2005). Chulalongkorn University Theses and Dissertations (Chula ETD). 65696.
https://digital.car.chula.ac.th/chulaetd/65696