{"id":809,"date":"2022-08-19T02:18:27","date_gmt":"2022-08-19T02:18:27","guid":{"rendered":"http:\/\/summergeometry.org\/sgi2022\/?p=809"},"modified":"2022-08-19T02:18:27","modified_gmt":"2022-08-19T02:18:27","slug":"proposing-a-less-expensive-algorithm-to-compute-isoperimetric-profiles-of-shapes-with-thin-necks","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2022\/proposing-a-less-expensive-algorithm-to-compute-isoperimetric-profiles-of-shapes-with-thin-necks\/","title":{"rendered":"Proposing a Less Expensive Algorithm to Compute Isoperimetric Profiles of Shapes with Thin Necks"},"content":{"rendered":"\n

By: Caroline Huber, Natalie Patten, and Xinyi Zhang<\/p>\n\n\n\n

On August 1st we began working on a project titled: \u201cTight Isoperimetric Profiles\u201d mentored by Richard Barnes of the Lawrence Berkeley National Lab and Michigan State University PhD student Erik Amezquita. <\/p>\n\n\n\n

We began the first week by looking at \u201cMedial Axis Isoperimetric Profiles\u201d (Zhang, DeFord, & Solomon, 2020). We read this alongside excerpts from provided materials, such as: Skiena\u2019s \u201cThe Algorithm Design Manual\u201d and Garey and Johnson\u2019s \u201cComputers and Intractability.\u201d <\/p>\n\n\n\n

Initial code was used to replicate the findings of \u201cMedial Axis Isoperimetric Profiles\u201d and to use this to extrapolate our own algorithm. The figure below shows the computation of the medial axis of a shape from the aforementioned code.<\/p>\n\n\n\n

\"\"
Figure 1: Medial Axis Computation<\/figcaption><\/figure>\n\n\n\n

The isoperimetric ratio (\\(\\frac{4\\pi*A}{p^2}\\)) of a shape with perimeter \\(p\\) and area \\(A\\) measures the compactness of said shape. To maximize the area and limit the perimeter of a shape, one would look for a shape with a high isoperimetric profile (the highest being a circle with a score of 1.0). However, for shapes with boundary perturbation, the ratio is unstable; hence the isoperimetric profile is used instead: \\(IP_{\\Omega}(t):=min\\{length({\\partial}F): F\\subseteq\\Omega \\& area(F)=t\\}\\).<\/p>\n\n\n\n

Currently, only brute-force methods exist for calculating isoperimetric profiles (IPs) of shapes with thin necks. Recent research, published in \u201cMedial Axis Isoperimetric Profiles\u201d has created a less expensive algorithm for computing IPs of shapes with thick necks, utilizing the concept of medial axes and graph nodes. By applying a greedy traversal along the medial axis of 2D shapes, this algorithm provides a tight bound for IPs of shapes with thick necks. However, the greedy traversal of adjacent nodes fails to provide a tight bound for IPs of shapes with thin necks. For example, Figure 2 is a clear illustration of the failure of the greedy traversal of adjacent nodes. In this case, the greedy traversal fails to capture the information of the large circle on the other side of the dumbbell due to the existence of a thin neck.<\/p>\n\n\n\n

\"\"
Figure 2: Shape with Thin Neck<\/figcaption><\/figure>\n\n\n\n

Thus, we have expanded on this research and revised the algorithm to formulate our proposed algorithm for shapes with thin necks. An overview of the algorithm-along with germane nomenclature-can be viewed below:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

To solve the problems created by the thin necks, we will partition the whole shape into different components according to its thin necks and define this new set of points as the set of centers of the largest circles in each component as \\(L\\). We will now apply the greedy algorithm not only to the adjacent points but also to the points in \\(L\\). In this way, we can solve the problems that cannot be solved by the original algorithm in cases like Figure 2 by capturing and encoding the information of the large circles on the other side of the thin necks in this \\(L\\) set. <\/p>\n\n\n\n

Some problems we anticipate this algorithm may encounter include:<\/p>\n\n\n\n

  1. Shapes with many thin necks<\/li>
  2. Shapes with different size \u201copenings\u201d on either side of its thin neck(s)<\/li><\/ol>\n\n\n\n

    We enjoyed working on this project and learning about isoperimetric profiles and the current research being done in this area. We also enjoyed learning about the different potential applications of this research\u2013for example, to examine possible gerrymandering.<\/p>\n","protected":false},"excerpt":{"rendered":"

    By: Caroline Huber, Natalie Patten, and Xinyi Zhang On August 1st we began working on a project titled: \u201cTight Isoperimetric Profiles\u201d mentored by Richard Barnes of the Lawrence Berkeley National Lab and Michigan State University PhD student Erik Amezquita.  We began the first week by looking at \u201cMedial Axis Isoperimetric Profiles\u201d (Zhang, DeFord, & Solomon, […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[138],"class_list":["post-809","post","type-post","status-publish","format-standard","hentry","category-research","tag-isoperimetric-profile"],"_links":{"self":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/809","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/comments?post=809"}],"version-history":[{"count":9,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/809\/revisions"}],"predecessor-version":[{"id":872,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/809\/revisions\/872"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/media?parent=809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/categories?post=809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/tags?post=809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}