ทฤษฎีบทของเรดอน
ในทางเรขาคณิตทฤษฎีบทของราดอนเกี่ยวกับเซตแบบนูน ซึ่งโย ฮันน์ ราดอนตีพิมพ์ในปี ค.ศ. 1921 ระบุว่า:
เซตของจุด d + 2 จุดใดๆ ในR dสามารถแบ่งออกเป็นสองเซตที่มีขอบนูนตัดกันได้
จุดตัดของส่วนนูนเหล่านี้เรียกว่าจุดเรดอนของเซต

ตัวอย่างเช่น ในกรณีที่d = 2 เซตของจุดสี่จุดใดๆ ในระนาบยุคลิดสามารถแบ่งออกได้สองวิธี วิธีแรกคือ อาจเกิดเป็นกลุ่มสามจุดและกลุ่มจุดเดียว โดยที่ส่วนนูนของกลุ่มสามจุด (รูปสามเหลี่ยม) จะครอบคลุมกลุ่มจุดเดียวนั้น หรืออีกวิธีหนึ่งคือ อาจเกิดเป็นคู่จุดสองคู่ที่เป็นจุดปลายของส่วนของเส้นตรง สองเส้น ที่ ตัดกัน
การพิสูจน์และการก่อสร้าง
พิจารณาชุดใด ๆมี จุด d + 2 จุดใน ปริภูมิ dมิติ ดังนั้นจึงมีเซตของตัวคูณa , ..., a ซึ่งไม่จำเป็นต้องเป็นศูนย์ทั้งหมด ที่สามารถแก้ระบบสมการเชิงเส้น ได้
เนื่องจากมี ตัวแปรที่ไม่ทราบค่า d + 2 ตัว (ตัวคูณ) แต่มีสมการที่ตัวแปรเหล่านั้นต้องสอดคล้องเพียงd + 1 สมการ (หนึ่งสมการสำหรับแต่ละพิกัดของจุด พร้อมกับสมการสุดท้ายที่กำหนดให้ผลรวมของตัวคูณเป็นศูนย์) กำหนดให้คำตอบที่ไม่เป็นศูนย์เฉพาะค่าหนึ่งคือa , ..., a ให้ ให้ เป็นเซตของจุดที่มีตัวคูณเป็นบวก และให้ให้ เป็นเซตของจุดที่มีตัวคูณเป็นค่าลบหรือศูนย์ จากนั้นและสร้างการแบ่งจุดตามที่ต้องการออกเป็นสองเซตย่อยที่มีส่วนนูนตัดกัน
เปลือกนูนของและเส้นทั้งสองต้องตัดกัน เพราะทั้งสองเส้นมีจุดนั้นอยู่
ที่ไหน
ด้านซ้ายของสูตรสำหรับแสดงจุดนี้ออกมาเป็นผลรวมนูนของจุดต่างๆ ในและด้านขวามือแสดงออกมาในรูปของการรวมกันแบบนูนของจุดต่างๆ ใน. ดังนั้น,เป็นส่วนหนึ่งของทั้งสองส่วนนูน ซึ่งเป็นการพิสูจน์เสร็จสมบูรณ์
วิธีการพิสูจน์นี้ช่วยให้สามารถสร้างจุด Radon ได้อย่างมีประสิทธิภาพภายในระยะเวลาที่เป็นพหุนามตามมิติ โดยใช้การกำจัดแบบเกาส์เซียนหรืออัลกอริทึมที่มีประสิทธิภาพอื่นๆ เพื่อแก้ระบบสมการสำหรับตัวคูณ[ 1 ]
ทฤษฎีบทเรดอนเชิงทอพอโลยี
รูปแบบที่เทียบเท่ากับทฤษฎีบทของราดอนคือ:
ถ้า ƒ เป็นฟังก์ชันเชิงเส้นตรง ใดๆ จากซิมเพล็กซ์ Δd +1 มิติ ( d + 1) ไปยังRdแล้วจะมีหน้าสองหน้าที่แยกจากกันของ Δd +1 ซึ่งภาพของหน้า ทั้ง สอง ภายใต้ ƒ จะตัดกัน
ทั้งสองอย่างเทียบเท่ากันเพราะฟังก์ชันเชิงเส้นใดๆ บนซิมเพล็กซ์จะถูกกำหนดอย่างไม่ซ้ำกันโดยภาพของจุดยอดของมัน ในทางคณิตศาสตร์ ให้ ƒ เป็นฟังก์ชันเชิงเส้นจาก Δ d+1ไปยังR dให้ให้ เป็นจุดยอดของ Δ d+1และให้เป็นภาพของพวกเขาภายใต้ƒตามสูตรดั้งเดิมสามารถแบ่งออกเป็นสองเซตย่อยที่ไม่ทับซ้อนกัน เช่น ( x ) และ ( x ) โดยมีขอบนูนที่ทับซ้อนกัน เนื่องจากfเป็นฟังก์ชันเชิงเส้น ขอบนูนของ ( x ) จึงเป็นภาพของหน้าที่เกิดจากจุดยอด ( v ) และในทำนองเดียวกัน ขอบนูนของ ( x )j ก็เป็นภาพของหน้าที่เกิดจากจุดยอด ( v )j หน้าทั้งสองนี้ไม่ทับซ้อนกัน และภาพของหน้าทั้งสองภายใต้fจะตัดกัน - ตามที่กล่าวอ้างโดยสูตรใหม่ทฤษฎีบท Radon ทางโทโพโลยีได้ขยายสูตรนี้ให้ทั่วไป โดยอนุญาตให้fเป็นฟังก์ชันต่อเนื่องใดๆ ก็ได้ - ไม่จำเป็นต้องเป็นฟังก์ชันเชิงเส้น: [ 2 ]
ถ้า ƒ เป็นฟังก์ชันต่อเนื่อง ใดๆ จาก ซิมเพ ล็กซ์มิติ ( d + 1) Δd +1ไปยังRd แล้วจะมีหน้าสองหน้าที่แยกจากกันของ Δd +1ซึ่งภาพของหน้าทั้งสองภายใต้ ƒ จะตัดกัน
โดยทั่วไปแล้ว ถ้าK เป็น เซตแบบนูนกระชับมิติ( d + 1) ใดๆ และ ƒ เป็นฟังก์ชันต่อเนื่องใดๆ จาก Kไปยัง ปริภูมิ dมิติ จะมีฟังก์ชันเชิงเส้นg อยู่ ซึ่งจุดบางจุดที่gมีค่าสูงสุดและจุดอื่นๆ ที่gมีค่าต่ำสุด จะถูกแมปโดย ƒ ไปยังจุดเดียวกัน ในกรณีที่Kเป็นซิมเพล็กซ์ หน้าซิมเพล็กซ์สองหน้าที่เกิดจากจุดสูงสุดและต่ำสุดของgจะต้องเป็นหน้าสองหน้าที่แยกจากกัน ซึ่งภาพของหน้าทั้งสองจะต้องมีส่วนตัดกันที่ไม่ว่างเปล่า ข้อความทั่วไปเดียวกันนี้ เมื่อนำไปใช้กับไฮเปอร์สเฟียร์แทนซิมเพล็กซ์ จะให้ทฤษฎีบท Borsuk–Ulamที่ว่า ƒ จะต้องแมปจุดสองจุดตรงข้ามของทรงกลมไปยังจุดเดียวกัน[ 2 ]
หลักฐาน
ทฤษฎีบทเรดอนเชิงทอพอโลยีได้รับการพิสูจน์ครั้งแรกโดย Ervin Bajmóczy และImre Bárány [ 2 ]ด้วยวิธีดังต่อไปนี้:
- สร้างแผนที่ต่อเนื่องจาก(เดอะทรงกลมหลายมิติ) ถึงโดยที่สำหรับทุกจุดบนทรงกลมและอยู่บนพื้นผิวสองด้านที่ไม่ทับซ้อนกันของ.
- นำทฤษฎีบทบอร์ซุก-อูแลมมา ใช้ กับฟังก์ชันซึ่งเป็นฟังก์ชันต่อเนื่องจากถึงทฤษฎีบทกล่าวว่า สำหรับฟังก์ชันใดๆ ดังกล่าว จะมีจุดบางจุดอยู่เสมอบนโดยที่.
- ประเด็นต่างๆและอยู่บนพื้นผิวสองด้านที่ไม่ทับซ้อนกันของและแผนที่เหล่านั้นถูกจัดทำโดยไปถึงจุดเดียวกันของนั่นหมายความว่าภาพของหน้าทั้งสองที่ไม่ทับซ้อนกันนั้นตัดกัน
หลักฐานอีกประการหนึ่งมอบให้โดยLászló LovászและAlexander Schrijver . [ 3 ]การพิสูจน์ครั้งที่สามมอบให้โดยJiří Matoušek : [ 4 ] : 115
- อนุญาตเป็นซิมเพล็กซ์และปล่อยให้เป็นการรวมที่ถูกลบของกับตัวมันเอง
- การรับรู้ทางเรขาคณิตของ มีรูปร่างเหมือนกับทรงกลมดังนั้นดัชนีZ ของเท่ากับ.
- ทฤษฎีบทเรดอนเชิงทอพอโลยีเป็นผลมาจากทฤษฎีบททั่วไปต่อไปนี้ สำหรับคอมเพล็กซ์เชิงซิมพลิเชียลใดๆถ้าดัชนี Z ของใหญ่กว่าจากนั้นสำหรับทุกการแมปต่อเนื่องจากถึงภาพของสองใบหน้าที่แยกจากกันของตัด.
แอปพลิเคชัน
จุด Radon ของจุดสี่จุดใดๆ บนระนาบคือค่ามัธยฐานทางเรขาคณิตซึ่งเป็นจุดที่ทำให้ผลรวมของระยะทางไปยังจุดอื่นๆ มีค่าน้อยที่สุด[ 5 ] [ 6 ]
ทฤษฎีบทของ Radon เป็นขั้นตอนสำคัญของการพิสูจน์มาตรฐานของทฤษฎีบทของ Hellyเกี่ยวกับจุดตัดของเซตแบบนูน[ 7 ]การพิสูจน์นี้เป็นแรงจูงใจให้ Radon ค้นพบทฤษฎีบทของ Radon ในครั้งแรก
ทฤษฎีบทของ Radon สามารถใช้คำนวณมิติ VCของ จุด dมิติโดยสัมพันธ์กับการแยกเชิงเส้นได้เช่นกัน มีเซตของจุดd + 1 จุด (เช่น จุดของซิมเพล็กซ์ปกติ) ซึ่งเซตย่อยที่ไม่ว่างสองเซตใดๆ สามารถแยกออกจากกันได้ด้วยไฮเปอร์เพลนอย่างไรก็ตาม ไม่ว่าเซตของจุดd + 2 จุดใดๆ ก็ตาม เซตย่อยสองเซตของพาร์ทิชัน Radon ไม่สามารถแยกออกจากกันด้วยเชิงเส้นได้ ดังนั้น มิติ VC ของระบบนี้จึงเท่ากับd + 1 พอดี [ 8 ]
อัลกอริทึมแบบสุ่มที่แทนที่ชุดจุดd + 2 จุดซ้ำๆ ด้วยจุด Radon ของพวกมัน สามารถใช้คำนวณค่าประมาณของจุดศูนย์กลางของชุดจุดใดๆ ได้ โดยใช้เวลาที่เป็นพหุนามทั้งในจำนวนจุดและมิติ[ 1 ]
แนวคิดที่เกี่ยวข้อง
ค่ามัธยฐานเชิงเรขาคณิตจุดเรดอนของจุดสามจุดในปริภูมิหนึ่งมิติก็คือค่ามัธยฐาน ของจุดเหล่านั้น นั่นเอง ค่า มัธยฐานเชิงเรขาคณิตของเซตของจุดคือจุดที่ทำให้ผลรวมของระยะทางไปยังจุดต่างๆ ในเซตนั้นมีค่าน้อยที่สุด มันเป็นการขยายแนวคิดของค่ามัธยฐานในปริภูมิหนึ่งมิติ และได้รับการศึกษาทั้งในแง่ของการกำหนดตำแหน่งสิ่งอำนวยความสะดวกและสถิติที่แข็งแกร่งสำหรับเซตของจุดสี่จุดในระนาบ ค่ามัธยฐานเชิงเรขาคณิตจะตรงกับจุดเรดอน
ทฤษฎีบทของทเวร์เบิร์กการวางนัยทั่วไปของการแบ่งส่วนออกเป็นrเซต ได้รับการเสนอโดยเฮลเกทเวร์เบิร์ก( 1966 )และปัจจุบันรู้จักกันในชื่อทฤษฎีบทของทเวร์เบิร์กทฤษฎีบทนี้กล่าวว่า สำหรับเซตใดๆ ของ สำหรับจุดในปริภูมิยูคลิดdมิติ จะมีการแบ่งเซตออกเป็นrเซตย่อย ซึ่งส่วนนูนของเซตย่อยเหล่านั้นจะตัดกันอย่างน้อยหนึ่งจุดร่วมกัน
ทฤษฎีบทของคาราเธโอโดรีกล่าวว่า จุดใดๆ ที่อยู่ในขอบเขตนูนของเซตของจุดบางเซต ก็จะอยู่ในขอบเขตนูนของเซตย่อยที่มีจุดไม่เกิน d + 1 จุดด้วย กล่าวคือ จุดที่กำหนดนั้นเป็นส่วนหนึ่งของพาร์ทิชันของราดอนซึ่งจุดนั้นเป็นจุดเดียว การพิสูจน์ทฤษฎีบทของคาราเธโอโดรีวิธีหนึ่งใช้เทคนิคการตรวจสอบคำตอบของระบบสมการเชิงเส้น คล้ายกับการพิสูจน์ทฤษฎีบทของราดอน เพื่อกำจัดจุดทีละจุดจนเหลือไม่เกิน d + 1 จุด
เรขาคณิตนูนแนวคิดที่เกี่ยวข้องกับทฤษฎีบทของ Radon ได้รับการพิจารณาสำหรับเรขาคณิตนูน ด้วยเช่นกัน ซึ่งเป็นตระกูลของเซตจำกัดที่มีคุณสมบัติว่าจุดตัดของเซตสองเซตใดๆ ในตระกูลยังคงอยู่ในตระกูล และเซตว่างและการรวมกันของเซตทั้งหมดอยู่ในตระกูล ในบริบททั่วไปนี้ เปลือกนูนของเซตSคือจุดตัดของสมาชิกในตระกูลที่ประกอบด้วยSและจำนวน Radon ของปริภูมิคือr ที่เล็กที่สุด ที่ จุด r ใดๆ มีสองเซตย่อยที่เปลือกนูนของเซตย่อยเหล่านั้นตัดกัน ในทำนองเดียวกัน เราสามารถกำหนดจำนวน Helly hและจำนวน Carathéodory cได้โดยการเปรียบเทียบกับคำจำกัดความของจำนวนเหล่านี้สำหรับเซตนูนในปริภูมิยุคลิด และสามารถแสดงได้ว่าจำนวนเหล่านี้เป็นไปตามอสมการh < r ≤ ch + 1 [ 9 ]
ทฤษฎีบทของ Radon สำหรับกราฟ ใน กราฟแบบไม่มีทิศทางใดๆเราอาจกำหนดเซตแบบนูนให้เป็นเซตของจุดยอดที่รวม เส้นทาง เหนี่ยว นำทุก เส้นทางที่เชื่อมต่อจุดยอดคู่หนึ่งในเซต ด้วยคำจำกัดความนี้ เซตของจุดยอด ω + 1 จุดในกราฟสามารถแบ่งออกเป็นสองเซตย่อยที่มีส่วนนูนตัดกัน และ ω + 1 คือจำนวนขั้นต่ำที่ทำให้สิ่งนี้เป็นไปได้ โดยที่ ω คือจำนวนคลิกของกราฟที่กำหนด[ 10 ]สำหรับผลลัพธ์ที่เกี่ยวข้องกับเส้นทางที่สั้นที่สุดแทนที่จะเป็นเส้นทางเหนี่ยวนำ โปรดดูChepoi (1986)และBandelt & Pesch (1989 )
หมายเหตุ
- 1 2คลาร์กสันและคณะ (1996 )
- 1 2 3บัจโมตซี, อีอีจี; บารานี, ไอ. (1979-09-01). "เรื่องทั่วไปทั่วไปของทฤษฎีบทของบ่อสุขและเรดอน" . Acta Mathematica Academiae Scientiarum Hungaricae . 34 (3): 347– 350. ดอย : 10.1007/BF01896131 . ISSN 1588-2632 . S2CID 12971298 .
- ↑ Lovász, László; Schrijver, Alexander (1998). "ทฤษฎีบท Borsuk สำหรับลิงก์ตรงข้ามและลักษณะสเปกตรัมของกราฟที่ฝังตัวได้โดยไม่มีลิงก์" Proceedings of the American Mathematical Society . 126 (5): 1275– 1285. doi : 10.1090/S0002-9939-98-04244-0 . ISSN 0002-9939 . S2CID 7790459 .
- ↑ Matoušek, Jiří (2007). การใช้ทฤษฎีบท Borsuk-Ulam : การบรรยายเกี่ยวกับวิธีการทางทอพอโลยีในคณิตศาสตร์เชิงการจัดเรียงและเรขาคณิต ( ฉบับที่ 2). เบอร์ลิน-ไฮเดลเบิร์ก: Springer-Verlag. ISBN 978-3-540-00362-5เขียน
ร่วมกับAnders BjörnerและGünter M. Ziegler
มาตรา 4.3 - ↑ Cieslik, Dietmar (2006), การเชื่อมต่อที่สั้นที่สุด: บทนำพร้อมการประยุกต์ใช้ในวิวัฒนาการชาติพันธุ์ , การเพิ่มประสิทธิภาพเชิงการจัดเรียง, เล่มที่17, Springer, หน้า6, ISBN 9780387235394.
- ↑ Plastria, Frank (2006), "ปัญหาการกำหนดตำแหน่งเฟอร์มาต์สี่จุดที่ได้รับการทบทวนใหม่ บทพิสูจน์ใหม่และการขยายผลลัพธ์เก่า" (PDF) , IMA Journal of Management Mathematics , 17 (4): 387– 396, doi : 10.1093/imaman/dpl007 , Zbl 1126.90046 , เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2016-03-04 , เรียกดูเมื่อ 2014-05-18 .
- ↑ Matoušek (2002) , หน้า 11.
- ↑ Epsilon-nets และ VC-dimension , บันทึกการบรรยายโดย Marco Pellegrini, 2004
- ↑เคย์และวอมเบิล (1971 )
- ↑ดูเชต์ (1987 )