Understanding the Medial Axis in Geometry
The medial axis in geometry is a fascinating concept related to Voronoi diagrams and maximal empty disks. Explore how the medial axis is constructed, its significance in the study of polygons, and its applications in modeling and algorithms. Learn about associated exercises and different algorithms for constructing the medial axis.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
S is a set of n points in the plane Vor(S) is the locus of centers of maximum empty disks. Vor(S) is the set of meeting points if the plane is burned uniformly and simultaneously from every site of S. Consider the boundary of a convex polygon P as the source of fire. The meeting points inside P realize the medial axis.
Medial axis The medial axis of M(P) of a polygon P is the closure of the sets of points in P that have two more closest points of the boundary of P.
Medial axis Each meeting point m in M(P) may be associated with time (i.e. distance) at which the fire reaches m, which is the radius of the maximal empty disk centered there.
Exercises: Show that the medial axis of a convex polygon can have a vertex of degree n. Compute the medial axis of a rectangle. What is the maximum and minimum number of edges the medial axis tree M(P) can have for a conve polygon with n vertices?
3D model of medial axis (Medial axis polyhedron) The z-direction of a point m on the medial axis represents the height which is equal to the radius of the maximal disk centered at m.
Construction of medial axis The Voronoi diagram and Medial axis is closely related. The Voronoi diagram sites are each edge with endpoints not included and the endpoints. The algorithm is: Construct the Voronoi diagram of the polygonal shape. Remove the edges incident on the concave vertices.
Construction of medial axis The Voronoi diagram and Medial axis is closely related. The Voronoi diagram sites are each edge with endpoints not included and the endpoints. The algorithm is: Construct the Voronoi diagram of the polygonal shape. Remove the edges incident on the concave vertices. O(nlogn) algorithm
Questions Prove that the first two bisectors of a convex polygon P to meet are adjacent. This algorithm for convex polygons can be implemented in O(nlogn) time using a priority queue.
Straight skeleton Presence of parabolic arcs in medial axis is problematic. The best algorithm known for this problem is O(n17/11). Note that the size of the skeleton of P is O(n)
