ส่วนย่อยสูงสุดของชุดจุดที่พอดีกับดิสก์ยูนิต
สมมติว่ามีชุด $P$ ของ $n$ ชี้บนเครื่องบินแล้วปล่อยให้ $P_1, \dots, P_k$ เป็นชุดย่อยที่แตกต่างกันของ $P$ ดังนั้นทุกจุดใน $P_i$ พอดีกับดิสก์หน่วยเดียวสำหรับทุกคน $i$, $1\le i\le k$.
ยิ่งไปกว่านั้นแต่ละ $P_i$ มีค่าสูงสุดกล่าวคือไม่มีดิสก์ยูนิตใดที่สามารถครอบคลุมส่วนย่อยของ $P$ นั่นคือซูเปอร์เซ็ตที่เข้มงวดของ $P_i$. พูดด้วยสายตาถ้าเราย้ายดิสก์หน่วยที่ครอบคลุม$P_i$ เพื่อปกปิดจุดที่ไม่อยู่ใน $P_i$จากนั้นอย่างน้อยหนึ่งจุดที่อยู่ในดิสก์นั้นจะถูกเปิดออก
นี่คือตัวอย่าง:
ในรูปด้านบนมีเซตย่อยสูงสุดสามชุด
ฉันไม่รู้ว่าปัญหานี้มีชื่อหรือเคยศึกษามาก่อน แต่นี่คือคำถามของฉัน
- สามารถ $k$ เป็นเลขชี้กำลังเกี่ยวกับ $n$เหรอ?
- ถ้าไม่เช่นนั้นเราจะหาเซตย่อยสูงสุดเหล่านั้นได้ในเวลาพหุนาม WRt $n$เหรอ?
ฉันคิดว่ามีชุดย่อยจำนวนมากที่อธิบายได้เนื่องจากอาร์กิวเมนต์ต่อไปนี้:
สมมติว่าจุดเป็นศูนย์กลางของดิสก์บางตัวที่มีรัศมี$1/2$. หากส่วนย่อยของจุดดังกล่าวพอดีในดิสก์ยูนิตก็จะรวมกันเป็นกลุ่ม เนื่องจากมี cliques จำนวนมากในชุดของดิสก์จึงควรมีชุดย่อยสูงสุดจำนวนมากแบบทวีคูณของชุดจุดเฉพาะนี้ที่พอดีกับดิสก์ยูนิต
คำตอบ
มากำหนดฟังก์ชั่นกัน $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $ส่งคืนคะแนนจำนวนหนึ่งจากเซต $P$ปกคลุมด้วยดิสก์ยูนิตโดยมีจุดศูนย์กลางอยู่ที่จุด $(x, y)$. นี่คือฟังก์ชันค่าคงที่แบบทีละชิ้นและง่ายที่จะเห็นว่าโดเมนของมันสามารถคิดว่าเป็นส่วนย่อยแบบระนาบซึ่งกำหนดโดยจุดตัดทั้งหมดของดิสก์ยูนิตโดยมีศูนย์กลางอยู่ที่จุดจากชุด$P$. การแบ่งส่วนนี้ประกอบด้วยจุดยอด (= จุดตัดกัน) ขอบ (= ส่วนโค้งวงกลม) และใบหน้า (= ชิ้นส่วนของระนาบโดยที่ฟังก์ชัน$f$ส่งคืนค่าเดียวกัน) เราจะบอกว่าใบหน้าเหล่านี้กำกับด้วยค่านี้
เราจะถือว่ากราฟระนาบที่กำหนดโดยการแบ่งย่อยนี้เป็นค่าปกติ 4 แบบ - เป็นสมมติฐานทั่วไปซึ่งหมายความว่าจุดทั้งหมดใน $P$อยู่ในตำแหน่งทั่วไป (จุดตัดแต่ละจุดเป็นของวงกลมสองวง) ตัวอย่างของการแบ่งย่อยดังกล่าวสำหรับ$n=3$ อยู่ด้านล่างซึ่งป้ายกำกับสำหรับแต่ละใบหน้า (รวมทั้งใบหน้าภายนอก) จะแสดงเป็นสีแดง
เท่าที่ฉันเข้าใจชุดย่อยสูงสุดของคุณ $P_i$สามารถเชื่อมโยงกับใบหน้าดังกล่าวของแผนกนี้ซึ่งมีป้ายขนาดใหญ่กว่าป้ายกำกับทั้งหมดของใบหน้าของพวกเขาที่อยู่ใกล้เคียง เป็นการตีความความหมายแบบคงที่ของความหมาย "ดิสก์เคลื่อนที่" ของคุณซึ่งคุณใช้ในคำจำกัดความของเซตย่อยสูงสุด
การแบ่งส่วนย่อยจะมีใบหน้าให้มากที่สุดเท่าที่จะเป็นไปได้ในกรณีที่วงกลมของหน่วยทั้งหมดตัดกันเป็นคู่กัน สามารถแสดงได้ว่าในกรณีนี้:
- จำนวนจุดยอดคือ $n(n-1)$
- จำนวนขอบคือ $2n(n-1)$
- จำนวนใบหน้าคือ $n(n-1)+2$
ดังนั้นคำตอบสำหรับคำถามของคุณคือ:
- ไม่หมายเลข $k$ ของส่วนย่อยสูงสุดคือ $O(n^2)$เนื่องจากต้องไม่เกินจำนวนใบหน้าทั้งหมด
- ใช่ชุดย่อยสูงสุดทั้งหมดสามารถพบได้ใน $O(n^3)$ เวลาโดยอัลกอริทึมการสแกนไร้เดียงสา
สำหรับชื่อของปัญหานี้ดูเหมือนว่ามันอาจเกี่ยวข้องกับรูปแบบบางอย่างของปัญหา Unit Disk Cover