ในเรขาคณิตระนาบแบบยุคลิดรูปสามเหลี่ยมเทียม ( pseudo-triangle ) คือเซตย่อยของระนาบที่เชื่อมต่อกันอย่างง่ายซึ่งอยู่ระหว่างเซตเว้า สามเซตที่สัมผัสกัน ดังนั้น มันจึงเป็นรูปทรงที่ล้อมรอบด้วยด้านโค้งเข้าด้านในสามด้าน ซึ่งเกิดจากขอบเขตของเซตเว้าทั้งสามนี้ การแบ่งรูปสามเหลี่ยมเทียม ( pseudotriangulations ) คือการแบ่งพื้นที่ของระนาบออกเป็นรูปสามเหลี่ยมเทียม และการแบ่งรูปสามเหลี่ยมเทียมแบบมีจุดยอดคือการแบ่งรูปสามเหลี่ยมเทียมที่ขอบที่แต่ละจุดยอดทำมุม กัน น้อยกว่า π

แม้ว่าคำว่า "pseudotriangle" และ "pseudotriangulation" จะถูกใช้ในความหมายต่างๆ ในทางคณิตศาสตร์มานานกว่ามาก^{[ 1 ]} แต่ คำศัพท์ที่ใช้ในที่นี้ได้รับการแนะนำในปี 1993 โดย Michel Pocchiola และ Gert Vegter ในส่วนที่เกี่ยวข้องกับการคำนวณความสัมพันธ์ของการมองเห็นและเส้นสัมผัสระหว่างสิ่งกีดขวางนูนในระนาบ pseudotriangulation ที่มีจุดยอดได้รับการพิจารณาครั้งแรกโดยIleana Streinu (2000, 2005) ในฐานะส่วนหนึ่งของวิธีแก้ปัญหาไม้บรรทัดช่างไม้ซึ่งเป็นการพิสูจน์ว่าเส้นทางรูปหลายเหลี่ยมง่ายๆ ใดๆ ในระนาบสามารถทำให้ตรงได้ด้วยลำดับของการเคลื่อนที่ต่อเนื่อง pseudotriangulation ยังถูกใช้สำหรับการตรวจจับการชนกันระหว่างวัตถุที่เคลื่อนที่^{[ 2 ]}และสำหรับการวาดกราฟแบบไดนามิกและการเปลี่ยนรูปร่าง^{[ 3 ]}การแบ่งสามเหลี่ยมเทียมแบบมีจุดเกิดขึ้นในทฤษฎีความแข็งแกร่งเป็นตัวอย่างของกราฟระนาบ ที่มี ^{ความแข็งแกร่งน้อยที่สุด [} 4 ^{] และ}ในวิธีการวางยามที่เกี่ยวข้องกับทฤษฎีหอศิลป์^{[ 5 ]}แอนติแมทรอยด์แบบเปลือกของเซตจุดระนาบทำให้เกิดการแบ่งสามเหลี่ยมเทียมแบบมีจุด^{[ 6 ]}แม้ว่าการแบ่งสามเหลี่ยมเทียมแบบมีจุดทั้งหมดจะไม่สามารถเกิดขึ้นได้ด้วยวิธีนี้

สำหรับการสำรวจรายละเอียดของเนื้อหาที่กล่าวถึงในที่นี้ โปรดดู Rote, SantosและStreinu (2008)

Pocchiola และ Vegter ( 1996a , 1996b , 1996c ) เดิมทีได้นิยามรูปสามเหลี่ยมเทียมว่าเป็นบริเวณที่เชื่อมต่อกันอย่างง่ายบนระนาบซึ่งล้อมรอบด้วยเส้นโค้งนูนเรียบสามเส้นที่สัมผัสกันที่จุดปลาย^{[ 7 ]}อย่างไรก็ตาม งานวิจัยต่อมาได้กำหนดนิยามที่กว้างขึ้นซึ่งใช้ได้กับรูปหลายเหลี่ยม โดยทั่วไป เช่นเดียวกับบริเวณที่ล้อมรอบด้วยเส้นโค้งเรียบ และอนุญาตให้มีมุมที่ไม่เป็นศูนย์ที่จุดยอดทั้งสาม ในนิยามที่กว้างขึ้นนี้ รูปสามเหลี่ยมเทียมเป็นบริเวณที่เชื่อมต่อกันอย่างง่ายบนระนาบซึ่งมีจุดยอดนูนสามจุด เส้นโค้งขอบเขตทั้งสามที่เชื่อมต่อจุดยอดทั้งสามนี้จะต้องเป็นเส้นโค้งนูน ในแง่ที่ว่าส่วนของเส้นตรงใดๆ ที่เชื่อมต่อจุดสองจุดบนเส้นโค้งขอบเขตเดียวกันจะต้องอยู่นอกหรือบนขอบเขตของรูปสามเหลี่ยมเทียมทั้งหมด ดังนั้น รูปสามเหลี่ยมเทียมจึงเป็นบริเวณระหว่างส่วนนูนของเส้นโค้งทั้งสามนี้ และโดยทั่วไปแล้ว เซตของเส้นโค้งนูนสามเซตใดๆ ที่สัมผัสกันจะก่อให้เกิดรูปสามเหลี่ยมเทียมที่อยู่ระหว่างเซตเหล่านั้น

สำหรับการใช้งานเชิงอัลกอริทึม การระบุลักษณะของรูปสามเหลี่ยมเทียมที่เป็นรูปหลายเหลี่ยมนั้นมีความสำคัญเป็นพิเศษ ในรูปหลายเหลี่ยม จุดยอดจะเป็นจุดนูนหากมีมุมภายในน้อยกว่า π และเป็นจุดเว้าหากเป็นอย่างอื่น (โดยเฉพาะอย่างยิ่ง เราถือว่ามุมที่มีค่าเท่ากับ π เป็นมุมเว้า) รูปหลายเหลี่ยมใดๆ ต้องมีมุมนูนอย่างน้อยสามมุม เนื่องจากผลรวมของมุมภายนอกของรูปหลายเหลี่ยมคือ 2π มุมนูนแต่ละมุมมีส่วนทำให้ผลรวมนี้มีค่าน้อยกว่า π และมุมเว้ามีส่วนทำให้ผลรวมเป็นศูนย์หรือติดลบ รูปสามเหลี่ยมเทียมที่เป็นรูปหลายเหลี่ยมคือรูปหลายเหลี่ยมที่มีจุดยอดนูนสามจุดพอดี โดยเฉพาะอย่างยิ่งรูปสามเหลี่ยม ใดๆ และรูปสี่เหลี่ยม ที่ไม่นูนใดๆ ก็ เป็นรูปสามเหลี่ยมเทียมได้

ขอบเขตนูนของรูปสามเหลี่ยมเสมือนใดๆ ก็คือรูปสามเหลี่ยม เส้นโค้งตามขอบเขตของรูปสามเหลี่ยมเสมือนระหว่างจุดยอดนูนแต่ละคู่จะอยู่ภายในรูปสามเหลี่ยมหรือทับซ้อนกับขอบด้านใดด้านหนึ่งของรูปสามเหลี่ยมนั้น

การแบ่งพื้นที่บนระนาบออกเป็นรูปสามเหลี่ยมเทียมเรียกว่า การแบ่งเป็นรูปสามเหลี่ยมเทียม (pseudotriangulation ) การแบ่งพื้นที่บนระนาบออกเป็นรูปสามเหลี่ยมใดๆ ก็ตาม ถือเป็นการแบ่งเป็นรูปสามเหลี่ยมเทียม แม้ว่าการแบ่งพื้นที่เดียวกันออกเป็นรูปสามเหลี่ยมสองรูปจะต้องมีจำนวนขอบและจำนวนสามเหลี่ยมเท่ากัน แต่สำหรับรูปสามเหลี่ยมเทียมนั้นไม่เป็นเช่นนั้น ตัวอย่างเช่น ถ้าพื้นที่นั้นเป็นรูปสามเหลี่ยมเทียมแบบหลายเหลี่ยมที่มีn จุดยอด การแบ่งเป็นรูปสามเหลี่ยมเทียมอาจมีรูปสามเหลี่ยมเทียมเพียงหนึ่งรูปและ nขอบ หรืออาจมีมากถึงn − 2 รูปและ 2 n − 3 ขอบก็ได้

การสร้างสามเหลี่ยมเทียมขั้นต่ำคือการสร้างสามเหลี่ยมเทียมTที่ไม่มีกราฟย่อยใดของTเป็นการสร้างสามเหลี่ยมเทียมที่ครอบคลุมบริเวณนูนเดียวกันของระนาบ การสร้างสามเหลี่ยมเทียมขั้นต่ำที่มีnจุดยอดจะต้องมีขอบอย่างน้อย 2n − 3 ขอบ หากมีขอบเพียง 2n − 3 ขอบ จะต้องเป็นการสร้างสามเหลี่ยมเทียมแบบมีจุดยอด แต่ก็มีการสร้างสามเหลี่ยมเทียมขั้นต่ำที่มีขอบ 3n − O(1) ขอบ^{[ 8 ]}

Agarwal et al. (2002) อธิบายโครงสร้างข้อมูลสำหรับการรักษารูปทรงสามเหลี่ยมเทียมของจุดเคลื่อนที่หรือรูปหลายเหลี่ยมเคลื่อนที่ พวกเขาแสดงให้เห็นว่าการใช้รูปทรงสามเหลี่ยมเทียมแทนรูปทรงสามเหลี่ยมธรรมดาช่วยให้อัลกอริธึมของพวกเขาสามารถรักษาโครงสร้างเหล่านี้ไว้ได้โดยมีการเปลี่ยนแปลงเชิงการจัดเรียงเพียงเล็กน้อยเมื่ออินพุตเคลื่อนที่ และพวกเขายังใช้รูปทรงสามเหลี่ยมเทียมแบบไดนามิกเหล่านี้ในการตรวจจับการชนกันระหว่างวัตถุที่เคลื่อนที่อีกด้วย

Gudmundsson et al. (2004) พิจารณาปัญหาการหาการสร้างรูปสามเหลี่ยมเทียมของชุดจุดหรือรูปหลายเหลี่ยมที่มีความยาวขอบรวมน้อยที่สุด และได้นำเสนออัลกอริทึมการประมาณค่าสำหรับปัญหานี้

การสร้างรูปสามเหลี่ยมเทียมแบบมีจุดยอดสามารถนิยามได้ว่าเป็นกลุ่มของส่วนของเส้นตรงที่ไม่ตัดกันและมีจำนวนจำกัด โดยที่ ณ จุดยอดแต่ละจุด ส่วนของเส้นตรงที่เชื่อมต่อกันจะทำมุมกันไม่เกิน π และไม่สามารถเพิ่มส่วนของเส้นตรงระหว่างจุดยอดสองจุดใดๆ ได้โดยยังคงรักษาคุณสมบัตินี้ไว้ เห็นได้ชัดว่าการสร้างรูปสามเหลี่ยมเทียมแบบมีจุดยอด คือการสร้างรูปสามเหลี่ยมเทียมของรูปทรงนูนของมันเอง กล่าวคือ สามารถเพิ่มขอบของรูปทรงนูนทั้งหมดได้โดยยังคงรักษาคุณสมบัติการทำมุมกันไว้ และหน้าภายในทั้งหมดต้องเป็นรูปสามเหลี่ยมเทียม มิฉะนั้น จะสามารถเพิ่มส่วนของเส้น ตรงสัมผัสสองเส้นระหว่างจุดยอดสองจุดของหน้าได้

การสร้างสามเหลี่ยมเทียมแบบมี จุดยอด vจุดจะต้องมีขอบ 2 v − 3 ขอบ พอดี ^{[ 9 ]}ซึ่งเป็นผลมาจากการนับซ้ำ อย่างง่าย ที่เกี่ยวข้องกับลักษณะเฉพาะของออยเลอร์ : เนื่องจากแต่ละหน้ายกเว้นหน้านอกสุดเป็นสามเหลี่ยมเทียมที่มีมุมนูนสามมุม การสร้างสามเหลี่ยมเทียมจะต้องมีมุมนูน 3 f − 3 มุมระหว่างขอบที่อยู่ติดกัน แต่ละขอบเป็นขอบ ตามเข็มนาฬิกาสำหรับสองมุม ดังนั้นจึงมีมุมทั้งหมด 2 eมุม ซึ่งทั้งหมด ยกเว้นvเป็นมุมนูน ดังนั้น 3 f − 3 = 2 e − vเมื่อรวมสมการนี้กับสมการของออยเลอร์f − e + v = 2 และแก้สมการเชิงเส้นพร้อมกัน ที่ได้ จะ ได้e = 2 v − 3 ด้วยเหตุผลเดียวกันนี้ จึงแสดงให้เห็นว่าf = v − 1 (รวมถึงส่วนนูนเป็นหนึ่งในหน้า) ดังนั้นการแบ่งเป็นรูปสามเหลี่ยมเทียมจะต้องมีรูปสามเหลี่ยมเทียมจำนวนv − 2 รูป พอดี

ในทำนองเดียวกัน เนื่องจาก กราฟย่อย kจุดยอดใดๆ ของ pseudotriangulation ที่มีจุดยอดสามารถทำให้สมบูรณ์เพื่อสร้าง pseudotriangulation ที่มีจุดยอดของจุดยอดได้ กราฟย่อยนั้นจะต้องมีขอบไม่เกิน 2k − 3 ขอบ ดังนั้น pseudotriangulation ที่มีจุดยอดจึงตรงตามเงื่อนไขที่กำหนดกราฟ Laman กล่าว คือ มี ขอบ 2v − 3 ขอบพอดี และ กราฟย่อย k จุดยอดของ กราฟย่อยเหล่านี้มีขอบไม่เกิน2k − 3 ขอบ กราฟ Laman และด้วยเหตุนี้ pseudotriangulation ที่มีจุดยอดจึงเป็นกราฟที่แข็งเกร็งน้อยที่สุดในสองมิติ กราฟ Laman ระนาบทุกกราฟสามารถวาดเป็น pseudotriangulation ที่มีจุดยอดได้ แม้ว่าการวาดระนาบของกราฟ Laman ระนาบทุกกราฟจะไม่ใช่ pseudotriangulation ก็ตาม^{[ 10 ]}

อีกวิธีหนึ่งในการหา pseudotriangulation ที่มีจุดคือการใช้shellกับชุดจุด กล่าวคือ การลบจุดยอดของ convex hull ทีละจุดจนกว่าจะลบจุดทั้งหมดออกไป ตระกูลของลำดับการลบที่สามารถสร้างขึ้นได้ด้วยวิธีนี้คือshelling antimatroidของชุดจุด และชุดของขอบของ convex hull ของลำดับของชุดจุดที่สร้างขึ้นโดยกระบวนการลบนี้จะสร้าง pseudotriangulation ขึ้นมา^{[ 6 ]}อย่างไรก็ตาม pseudotriangulation ที่มีจุดทั้งหมดไม่สามารถสร้างขึ้นได้ด้วยวิธีนี้

Aichholzer et al. (2004) แสดงให้เห็นว่าเซตของ จุด nจุดซึ่งh จุดอยู่ใน ส่วนนูนของเซต จะต้องมีpseudotriangulation ที่แตกต่างกัน อย่างน้อย C ×3 ^{n − h} แบบ โดยที่ C หมายถึงจำนวน Catalan ที่ i ผลที่ตาม มาคือ พวกเขาแสดงให้เห็นว่าเซตของจุดที่มี pseudotriangulation น้อยที่สุดคือเซตของจุดยอดของรูปหลายเหลี่ยมนูน Aichholzer et al. (2006) ศึกษาเซตของจุดที่มี pseudotriangulation จำนวนมาก นักวิจัยด้านเรขาคณิตเชิงคำนวณยังได้จัดเตรียมอัลกอริทึมสำหรับการแสดงรายการ pseudotriangulation ทั้งหมดของเซตของจุดในเวลาอันสั้นต่อ pseudotriangulation ^{[ 11 ]}

• ส่วนโค้งเดลทอยด์
• สามเหลี่ยมวงกลม