Computational Geometry: Understanding Point-Line Duality
Explore the concept of Point-Line Duality in computational geometry, as explained by Michael Goodrich with slides from Carola Wenk. Understand the properties and relationships between primal points, lines, dual planes, and more through insightful explanations and visual aids.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Computational Geometry Point-Line Duality Michael Goodrich with slides from Carola Wenk 1
Point-Line Duality Let ? = ?1, ,?? 2 be a set of ? points. Now define a set ? = ?1 of ? lines as follows: , ,?? Dual plane Line: ? :? = ??? ?? Point: ? = (?, ?) Primal plane Point: ? = (??,??) Line: ?:? = ?? + ? p*1 l2 l1 p3 p*2 l*1 p4 p1 l*2 p*3 p2 p*4 2
Primal plane Point: ? = (??,??) Line: ?:? = ?? + ? Dual plane Line: ? :? = ??? ?? Point: ? = (?, ?) Properties Dual Primal p*1 l2 l1 p3 p*2 l*1 p4 p1 l*2 p*3 p2 p*4 ? = ? ? ? ? ? incidence-preserving ? lies above ? ? lies above ? p1 l2 l*2 p*1 p3 is above l1 l*1 is above p*3 3
Primal plane Point: ? = (??,??) Line: ?:? = ?? + ? Dual plane Line: ? :? = ??? ?? Point: ? = (?, ?) Properties Dual Primal p*1 l1 l*1 p1 p*2 p2 Points ?1 and ?2 lie on line ?1 and ?2 contain Lines ?1 point ?1 4
Point-Line Duality Puzzle l*2 p1 l1 l2 p*2 l*1 p*3 p*4 p4 p*1 p3 p2 ?1 lies above ?1 ?2 lies on ?2 lies on ?3lies below ?1 ?4 lies above ?2 ?1 ?2 ?2 ?3 ?4 ?1 ?1 lies above lies on lies on lies below lies above ?1 ?2 ?2 ?1 ?2 5
Primal plane Point: ? = (??,??) Line: ?:? = ?? + ? Dual plane Line: ? :? = ??? ?? Point: ? = (?, ?) LCH UE Dual Primal p*2 p*1 p*3 p*4 p1 p5 p2 p4 p3 p*5 LCH lower convex hull UE upper envelope (= pointwise maximum) = halfplane intersection (of upper halfplanes) LCH = p1, p2, p3, p4, p5 UE = p*1, p*2, p*3, p*4, p*5 6
