Feb 02: Building a segment arrangement

views comments

Too much snow; we're remote again.
Intersecting pairs ≥ intersection points
Bentley-Ottman implicitly perturbs coincident intersections alart, but not necessarily in a geometrically consistent way
Modified event queue records all segments associated with each event point.
Implement event queue using a balanced BST (to detect duplicates)
O(d log n) time to handle each event, where d = degree of arrgh vertex
Overall running time is O((n+I) log n) by Euler's formula

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois

Related Media