Toussaint (1986)ได้นำเสนออัลกอริทึมที่มีประสิทธิภาพสำหรับการสร้างโครงร่างนูนสัมพัทธ์สำหรับเซตจุดจำกัดภายในรูป หลายเหลี่ยม แบบง่าย^{[ 3 ]}ด้วยการปรับปรุงขอบเขตเวลาสำหรับสองรูทีนย่อย การค้นหาเส้นทางที่สั้นที่สุดระหว่างจุดสอบถามในรูปหลายเหลี่ยม^{[ 4 ]}และการสร้างสามเหลี่ยมของรูปหลายเหลี่ยม^{[ 5 ]}อัลกอริทึมนี้ใช้เวลา${\displaystyle O(p+n\log(p+n))}$บนอินพุตด้วย${\displaystyle n}$จุดในรูปหลายเหลี่ยมที่มี${\displaystyle p}$จุดยอด^{[ 4 ]}นอกจากนี้ยังสามารถบำรุงรักษาแบบไดนามิกได้ในเวลาย่อยเชิงเส้นต่อการอัปเดต^{[ 6 ]}

ขอบเขตความนูนสัมพัทธ์ของเซตจุดจำกัดนั้นจะเป็นรูปหลายเหลี่ยมแบบง่ายอย่างอ่อน เสมอ แต่ในความเป็นจริงแล้วมันอาจไม่ใช่รูปหลายเหลี่ยมแบบง่ายก็ได้ เพราะบางส่วนของมันอาจเชื่อมต่อกันด้วยส่วนของเส้นตรงหรือเส้นทางรูปหลายเหลี่ยม แทนที่จะเป็นบริเวณที่มีพื้นที่ไม่เป็นศูนย์

สำหรับขอบนูนสัมพัทธ์ของรูปหลายเหลี่ยมแบบง่าย สามารถใช้นิยามความนูนแบบอื่นที่เทียบเท่ากันได้ รูปหลายเหลี่ยมแบบง่าย${\displaystyle P}$ภายในรูปหลายเหลี่ยมธรรมดาอีกรูปหนึ่ง${\displaystyle Q}$มีความนูนค่อนข้างมากหรือ${\displaystyle Q}$-นูน ถ้าทุกส่วนของเส้นตรงที่บรรจุอยู่ภายใน${\displaystyle Q}$ที่เชื่อมต่อจุดสองจุด${\displaystyle P}$อยู่ภายใน${\displaystyle P}$. ขอบเขตความนูนสัมพัทธ์ของรูปหลายเหลี่ยมอย่างง่าย${\displaystyle P}$ภายใน${\displaystyle Q}$สามารถนิยามได้ว่าเป็นจุดตัดของทั้งหมด${\displaystyle Q}$-รูปหลายเหลี่ยมนูนที่ประกอบด้วย${\displaystyle P}$เนื่องจากมีขนาดเล็กที่สุด${\displaystyle Q}$- รูปหลายเหลี่ยมนูนที่ประกอบด้วย${\displaystyle P}$หรือในรูปหลายเหลี่ยมแบบง่ายที่มีเส้นรอบรูปน้อยที่สุดที่บรรจุอยู่ภายใน${\displaystyle P}$และถูกจำกัดโดย${\displaystyle Q}$[ ^{1 ]​}

Klette (2010)ขยาย อัลกอริทึม เวลาเชิงเส้นสำหรับขอบนูนของรูปหลายเหลี่ยมแบบง่ายไปสู่ขอบนูนสัมพัทธ์ของรูปหลายเหลี่ยมแบบง่ายรูปหนึ่งภายในอีกรูปหนึ่ง อย่างไรก็ตาม อัลกอริทึมที่ขยายแล้วนี้ไม่ใช่เวลาเชิงเส้น ความซับซ้อนของเวลาขึ้นอยู่กับความลึกของการซ้อนของคุณลักษณะบางอย่างของรูปหลายเหลี่ยมรูปหนึ่งภายในอีกรูปหนึ่ง ในกรณีนี้ ขอบนูนสัมพัทธ์ก็คือรูปหลายเหลี่ยมแบบง่ายนั่นเอง^{[ 1 ]}อัลกอริทึมเวลาเชิงเส้นทางเลือกที่อิงตามการวางแผนเส้นทางเป็นที่รู้จัก^{[ 7 ]}

นิยามที่คล้ายกันนี้สามารถกำหนดให้กับขอบเขตความนูนสัมพัทธ์ของรูปหลายเหลี่ยมธรรมดาสองรูปที่แยกจากกันได้ ขอบเขตประเภทนี้สามารถใช้ในอัลกอริธึมสำหรับการทดสอบว่ารูปหลายเหลี่ยมทั้งสองสามารถแยกออกเป็นระนาบครึ่งที่ไม่ทับซ้อนกันได้หรือไม่โดยการเคลื่อนที่เชิงเส้นต่อเนื่อง^{[ 8 ]}และในโครงสร้างข้อมูลสำหรับการตรวจจับการชนกันของรูปหลายเหลี่ยมที่เคลื่อนที่^{[ 9 ]}