กลับไปหน้าบทความ

อ่าน 8 นาที

ทฤษฎีบทของเรดอน

CS1 แหล่งที่มาภาษารัสเซีย (ru)/ตัวถังนูน/ทฤษฎีเส้นตัดขวางเรขาคณิต/ทฤษฎีบทในเรขาคณิตนูน/ทฤษฎีบทในเรขาคณิตไม่ต่อเนื่อง

ในทางเรขาคณิตทฤษฎีบทของราดอนเกี่ยวกับเซตแบบนูน ซึ่งโย ฮันน์ ราดอนตีพิมพ์ในปี ค.ศ. 1921 ระบุว่า:

ทฤษฎีบทของเรดอน

ในทางเรขาคณิตทฤษฎีบทของราดอนเกี่ยวกับเซตแบบนูน ซึ่งโย ฮันน์ ราดอนตีพิมพ์ในปี ค.ศ. 1921 ระบุว่า:

เซตของจุด d  +  2 จุดใดๆ ในR dสามารถแบ่งออกเป็นสองเซตที่มีขอบนูนตัดกันได้

จุดตัดของส่วนนูนเหล่านี้เรียกว่าจุดเรดอนของเซต

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

ตัวอย่างเช่น ในกรณีที่d  =  2 เซตของจุดสี่จุดใดๆ ในระนาบยุคลิดสามารถแบ่งออกได้สองวิธี วิธีแรกคือ อาจเกิดเป็นกลุ่มสามจุดและกลุ่มจุดเดียว โดยที่ส่วนนูนของกลุ่มสามจุด (รูปสามเหลี่ยม) จะครอบคลุมกลุ่มจุดเดียวนั้น หรืออีกวิธีหนึ่งคือ อาจเกิดเป็นคู่จุดสองคู่ที่เป็นจุดปลายของส่วนของเส้นตรง สองเส้น ที่ ตัดกัน

การพิสูจน์และการก่อสร้าง

พิจารณาชุดใด ๆX={x1,x2,,x+2}อาร์{\displaystyle X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}}มี จุด d  +  2 จุดใน ปริภูมิ dมิติ ดังนั้นจึงมีเซตของตัวคูณa ,  ..., a ซึ่งไม่จำเป็นต้องเป็นศูนย์ทั้งหมด ที่สามารถแก้ระบบสมการเชิงเส้น ได้ 

ฉัน=1+2เอฉันxฉัน=0,ฉัน=1+2เอฉัน=0,{\displaystyle \sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0,}

เนื่องจากมี ตัวแปรที่ไม่ทราบค่า d  +  2 ตัว (ตัวคูณ) แต่มีสมการที่ตัวแปรเหล่านั้นต้องสอดคล้องเพียงd  +  1 สมการ (หนึ่งสมการสำหรับแต่ละพิกัดของจุด พร้อมกับสมการสุดท้ายที่กำหนดให้ผลรวมของตัวคูณเป็นศูนย์) กำหนดให้คำตอบที่ไม่เป็นศูนย์เฉพาะค่าหนึ่งคือa ,  ..., a ให้ ฉันX{\displaystyle I\subseteq X}ให้ เป็นเซตของจุดที่มีตัวคูณเป็นบวก และให้เจ=Xฉัน{\displaystyle J=X\setminus I}ให้ เป็นเซตของจุดที่มีตัวคูณเป็นค่าลบหรือศูนย์ จากนั้นฉัน{\displaystyle I}และเจ{\displaystyle J}สร้างการแบ่งจุดตามที่ต้องการออกเป็นสองเซตย่อยที่มีส่วนนูนตัดกัน

เปลือกนูนของฉัน{\displaystyle I}และเจ{\displaystyle J}เส้นทั้งสองต้องตัดกัน เพราะทั้งสองเส้นมีจุดนั้นอยู่

พี=xฉันฉันเอฉันเอxฉัน=xเจเจเอเจเอxเจ,{\displaystyle p=\sum _{x_{i}\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{x_{j}\in J}{\frac {-a_{j}}{A}}x_{j},}

ที่ไหน

เอ=xฉันฉันเอฉัน=xเจเจเอเจ.{\displaystyle A=\sum _{x_{i}\in I}a_{i}=-\sum _{x_{j}\in J}a_{j}.}

ด้านซ้ายของสูตรสำหรับพี{\displaystyle p}แสดงจุดนี้ออกมาเป็นผลรวมนูนของจุดต่างๆ ในฉัน{\displaystyle I}และด้านขวามือแสดงออกมาในรูปของการรวมกันแบบนูนของจุดต่างๆ ในเจ{\displaystyle J}. ดังนั้น,พี{\displaystyle p}เป็นส่วนหนึ่งของทั้งสองส่วนนูน ซึ่งเป็นการพิสูจน์เสร็จสมบูรณ์

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

ทฤษฎีบทเรดอนเชิงทอพอโลยี

รูปแบบที่เทียบเท่ากับทฤษฎีบทของราดอนคือ:

ถ้า ƒ เป็นฟังก์ชันเชิงเส้นตรง ใดๆ จากซิมเพล็กซ์ Δd +1 มิติ ( d  +  1) ไปยังRdแล้วจะมีหน้าสองหน้าที่แยกจากกันของ Δd +1 ซึ่งภาพของหน้า ทั้ง สอง ภายใต้ ƒ จะตัดกัน

ทั้งสองอย่างเทียบเท่ากันเพราะฟังก์ชันเชิงเส้นใดๆ บนซิมเพล็กซ์จะถูกกำหนดอย่างไม่ซ้ำกันโดยภาพของจุดยอดของมัน ในทางคณิตศาสตร์ ให้ ƒ เป็นฟังก์ชันเชิงเส้นจาก Δ d+1ไปยังR dให้วี1,วี2,,วี+2{\displaystyle v_{1},v_{2},\dots ,v_{d+2}}ให้ เป็นจุดยอดของ Δ d+1และให้x1,x2,,x+2{\displaystyle x_{1},x_{2},\dots ,x_{d+2}}เป็นภาพของพวกเขาภายใต้ƒตามสูตรดั้งเดิมx1,x2,,x+2{\displaystyle x_{1},x_{2},\dots ,x_{d+2}}สามารถแบ่งออกเป็นสองเซตย่อยที่ไม่ทับซ้อนกัน เช่น ( 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 ]ด้วยวิธีดังต่อไปนี้:

  • สร้างแผนที่ต่อเนื่องจี{\displaystyle g}จากเอส{\displaystyle S^{d}}(เดอะ{\displaystyle d}ทรงกลมหลายมิติ) ถึงΔ+1{\displaystyle \Delta ^{d+1}}โดยที่สำหรับทุกจุดx{\displaystyle x}บนทรงกลมจี(x){\displaystyle g(x)}และจี(x){\displaystyle g(-x)}อยู่บนพื้นผิวสองด้านที่ไม่ทับซ้อนกันของΔ+1{\displaystyle \Delta ^{d+1}}.
  • นำทฤษฎีบทบอร์ซุก-อูแลมมา ใช้ กับฟังก์ชันเอฟจี{\displaystyle f\circ g}ซึ่งเป็นฟังก์ชันต่อเนื่องจากเอส{\displaystyle S^{d}}ถึงอาร์{\displaystyle \mathbb {R} ^{d}}ทฤษฎีบทกล่าวว่า สำหรับฟังก์ชันใดๆ ดังกล่าว จะมีจุดบางจุดอยู่เสมอy{\displaystyle y}บนเอส{\displaystyle S^{d}}โดยที่เอฟ(จี(y))=เอฟ(จี(y)){\displaystyle f(g(y))=f(g(-y))}.
  • ประเด็นต่างๆจี(y){\displaystyle g(y)}และจี(y){\displaystyle g(-y)}อยู่บนพื้นผิวสองด้านที่ไม่ทับซ้อนกันของΔ+1{\displaystyle \Delta ^{d+1}}และแผนที่เหล่านั้นถูกจัดทำโดยเอฟ{\displaystyle f}ไปถึงจุดเดียวกันของอาร์{\displaystyle \mathbb {R} ^{d}}นั่นหมายความว่าภาพของหน้าทั้งสองที่ไม่ทับซ้อนกันนั้นตัดกัน

หลักฐานอีกประการหนึ่งมอบให้โดยLászló LovászและAlexander Schrijver . [ 3 ]การพิสูจน์ครั้งที่สามมอบให้โดยJiří Matoušek : [ 4 ] : 115

  • อนุญาตเค{\displaystyle K}เป็นซิมเพล็กซ์Δ+1{\displaystyle \Delta ^{d+1}}และปล่อยให้เคΔ*2{\displaystyle K_{\Delta }^{*2}}เป็นการรวมที่ถูกลบของเค{\displaystyle K}กับตัวมันเอง
  • การรับรู้ทางเรขาคณิตของเคΔ*2{\displaystyle K_{\Delta }^{*2}} มีรูปร่างเหมือนกับทรงกลมเอส+1{\displaystyle S^{d+1}}ดังนั้นดัชนีZ ของเคΔ*2{\displaystyle K_{\Delta }^{*2}}เท่ากับ+1{\displaystyle d+1}.
  • ทฤษฎีบทเรดอนเชิงทอพอโลยีเป็นผลมาจากทฤษฎีบททั่วไปต่อไปนี้ สำหรับคอมเพล็กซ์เชิงซิมพลิเชียลใดๆเค{\displaystyle K}ถ้าดัชนี Z ของเคΔ*2{\displaystyle K_{\Delta }^{*2}}ใหญ่กว่า{\displaystyle d}จากนั้นสำหรับทุกการแมปต่อเนื่องจากเค{\displaystyle \|K\|}ถึงอาร์{\displaystyle \mathbb {R} ^{d}}ภาพของสองใบหน้าที่แยกจากกันของเค{\displaystyle K}ตัด.

แอปพลิเคชัน

จุด 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 )และปัจจุบันรู้จักกันในชื่อทฤษฎีบทของทเวร์เบิร์กทฤษฎีบทนี้กล่าวว่า สำหรับเซตใดๆ ของ (+1)(1)+1 {\displaystyle (d+1)(r-1)+1\ }สำหรับจุดในปริภูมิยูคลิดdมิติ จะมีการแบ่งเซตออกเป็นrเซตย่อย ซึ่งส่วนนูนของเซตย่อยเหล่านั้นจะตัดกันอย่างน้อยหนึ่งจุดร่วมกัน

ทฤษฎีบทของคาราเธโอโดรีกล่าวว่า จุดใดๆ ที่อยู่ในขอบเขตนูนของเซตของจุดบางเซต ก็จะอยู่ในขอบเขตนูนของเซตย่อยที่มีจุดไม่เกิน d  + 1 จุดด้วย กล่าวคือ จุดที่กำหนดนั้นเป็นส่วนหนึ่งของพาร์ทิชันของราดอนซึ่งจุดนั้นเป็นจุดเดียว การพิสูจน์ทฤษฎีบทของคาราเธโอโดรีวิธีหนึ่งใช้เทคนิคการตรวจสอบคำตอบของระบบสมการเชิงเส้น คล้ายกับการพิสูจน์ทฤษฎีบทของราดอน เพื่อกำจัดจุดทีละจุดจนเหลือไม่เกิน d  + 1 จุด

เรขาคณิตนูนแนวคิดที่เกี่ยวข้องกับทฤษฎีบทของ Radon ได้รับการพิจารณาสำหรับเรขาคณิตนูน ด้วยเช่นกัน ซึ่งเป็นตระกูลของเซตจำกัดที่มีคุณสมบัติว่าจุดตัดของเซตสองเซตใดๆ ในตระกูลยังคงอยู่ในตระกูล และเซตว่างและการรวมกันของเซตทั้งหมดอยู่ในตระกูล ในบริบททั่วไปนี้ เปลือกนูนของเซตSคือจุดตัดของสมาชิกในตระกูลที่ประกอบด้วยSและจำนวน Radon ของปริภูมิคือr ที่เล็กที่สุด ที่ จุด r ใดๆ มีสองเซตย่อยที่เปลือกนูนของเซตย่อยเหล่านั้นตัดกัน ในทำนองเดียวกัน เราสามารถกำหนดจำนวน Helly hและจำนวน Carathéodory cได้โดยการเปรียบเทียบกับคำจำกัดความของจำนวนเหล่านี้สำหรับเซตนูนในปริภูมิยุคลิด และสามารถแสดงได้ว่าจำนวนเหล่านี้เป็นไปตามอสมการh  < rch + 1 [ 9 ]     

ทฤษฎีบทของ Radon สำหรับกราฟ ใน กราฟแบบไม่มีทิศทางใดๆเราอาจกำหนดเซตแบบนูนให้เป็นเซตของจุดยอดที่รวม เส้นทาง เหนี่ยว นำทุก เส้นทางที่เชื่อมต่อจุดยอดคู่หนึ่งในเซต ด้วยคำจำกัดความนี้ เซตของจุดยอด ω  +  1 จุดในกราฟสามารถแบ่งออกเป็นสองเซตย่อยที่มีส่วนนูนตัดกัน และ ω  +  1 คือจำนวนขั้นต่ำที่ทำให้สิ่งนี้เป็นไปได้ โดยที่ ω คือจำนวนคลิกของกราฟที่กำหนด[ 10 ]สำหรับผลลัพธ์ที่เกี่ยวข้องกับเส้นทางที่สั้นที่สุดแทนที่จะเป็นเส้นทางเหนี่ยวนำ โปรดดูChepoi (1986)และBandelt & Pesch (1989 )

หมายเหตุ

  1. 1 2คลาร์กสันและคณะ (1996 )
  2. 1 2 3บัจโมตซี, อีอีจี; บารานี, ไอ. (1979-09-01). "เรื่องทั่วไปทั่วไปของทฤษฎีบทของบ่อสุขและเรดอน" . Acta Mathematica Academiae Scientiarum Hungaricae . 34 (3): 347– 350. ดอย : 10.1007/BF01896131 . ISSN 1588-2632 . S2CID 12971298 .  
  3. 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 .  
  4. Matoušek, Jiří (2007). การใช้ทฤษฎีบท Borsuk-Ulam : การบรรยายเกี่ยวกับวิธีการทางทอพอโลยีในคณิตศาสตร์เชิงการจัดเรียงและเรขาคณิต ( ฉบับที่ 2). เบอร์ลิน-ไฮเดลเบิร์ก: Springer-Verlag. ISBN  978-3-540-00362-5เขียนร่วมกับAnders BjörnerและGünter M. Zieglerมาตรา 4.3
  5. Cieslik, Dietmar (2006), การเชื่อมต่อที่สั้นที่สุด: บทนำพร้อมการประยุกต์ใช้ในวิวัฒนาการชาติพันธุ์ , การเพิ่มประสิทธิภาพเชิงการจัดเรียง, เล่มที่17, Springer, หน้า6, ISBN   9780387235394.
  6. 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 .
  7. Matoušek (2002) , หน้า 11.
  8. Epsilon-nets และ VC-dimension , บันทึกการบรรยายโดย Marco Pellegrini, 2004
  9. เคย์และวอมเบิล (1971 )
  10. ดูเชต์ (1987 )
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Radon%27s_theorem&oldid=1362921014 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ทฤษฎีบทของเรดอน

ในทางเรขาคณิตทฤษฎีบทของราดอนเกี่ยวกับเซตแบบนูน ซึ่งโย ฮันน์ ราดอนตีพิมพ์ในปี ค.ศ. 1921 ระบุว่า:

การพิสูจน์และการก่อสร้าง

พิจารณาชุดใด ๆ X = { x 1 , x 2 , … , x ง + 2 } ⊂ อาร์ ง {\displaystyle X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}} มี จุด d + 2 จุดใน ปริภูมิ d มิติ ดังนั้นจึงมีเซตของตัวคูณ a , ...

ทฤษฎีบทเรดอนเชิงทอพอโลยี

รูปแบบที่เทียบเท่ากับทฤษฎีบทของราดอนคือ:

หลักฐาน

ทฤษฎีบทเรดอนเชิงทอพอโลยีได้รับการพิสูจน์ครั้งแรกโดย Ervin Bajmóczy และ Imre Bárány [ 2 ] ด้วยวิธีดังต่อไปนี้: