Geometric Realization

import%20marimo%0A%0A__generated_with%20%3D%20%220.17.6%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20nav_menu%20%3D%20mo.nav_menu(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%2Findex.html%22%3A%20f%22%7Bmo.icon('lucide%3Ahome')%7D%20Home%22%2C%0A%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20orientation%3D%22vertical%22%2C%0A%20%20%20%20)%0A%20%20%20%20nav_menu%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Abstract%20Simplicial%20Complexes%20and%20Geometric%20Realization%0A%0A%20%20%20%20In%20topological%20data%20analysis%2C%20we%20often%20construct%20simplicial%20complexes%20from%20data%2C%20but%20it's%20important%20to%20distinguish%20between%20two%20closely%20related%20notions%3A%0A%0A%20%20%20%20-%20Abstract%20simplicial%20complexes%3A%20purely%20combinatorial%20structures%3B%0A%20%20%20%20-%20Geometric%20realizations%3A%20embeddings%20of%20these%20combinatorial%20structures%20into%20Euclidean%20space.%0A%0A%20%20%20%20This%20notebook%20provides%20a%20simple%20illustration%20of%20both%20concepts.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Abstract%20Simplicial%20Complexes%0A%0A%20%20%20%20Given%20a%20finite%20set%20of%20vertices%20%24V%24%2C%20an%20abstract%20simplicial%20complex%20is%20a%20collection%20of%20finite%20subsets%20of%20%24V%24%20that%20is%20closed%20under%20inclusion.%20That%20is%2C%20if%20%24%5Csigma%20%5Csubseteq%20V%24%20is%20in%20the%20complex%2C%20then%20every%20subset%20of%20%24%5Csigma%24%20is%20also%20in%20the%20complex.%0A%0A%20%20%20%20In%20this%20notebook%2C%20we%20simply%20construct%20the%20full%20simplex%20on%20a%20given%20vertex%20set%3A%20that%20is%2C%20the%20set%20of%20all%20possible%20non-empty%20subsets%20of%20%24V%24.%0A%0A%20%20%20%20For%20example%2C%20with%20%245%24%20vertices%20%24%5C%7BA%2C%20B%2C%20C%2C%20D%2C%20E%5C%7D%24%2C%20the%20full%20simplicial%20complex%20consists%20of%3A%0A%0A%20%20%20%20-%20%245%24%20vertices%20(%240%24-simplices)%2C%0A%20%20%20%20-%20%2410%24%20edges%20(%241%24-simplices)%2C%0A%20%20%20%20-%20%2410%24%20triangles%20(%242%24-simplices)%2C%0A%20%20%20%20-%20%245%24%20tetrahedra%20(%243%24-simplices)%2C%0A%20%20%20%20-%20%241%24%20full%20%244%24-simplex%20(the%20entire%20vertex%20set).%0A%0A%20%20%20%20This%20is%20simply%20the%20combinatorial%20power%20set%20(minus%20the%20empty%20set).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20itertools%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20def%20is_simplex(vertices%2C%20subset)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Check%20if%20a%20subset%20is%20a%20valid%20simplex%20(non-empty%20subset%20of%20the%20vertex%20set).%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20return%20set(subset).issubset(vertices)%20and%20len(subset)%20%3E%200%0A%0A%20%20%20%20def%20construct_simplicial_complex(vertices)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Construct%20the%20full%20simplicial%20complex%20consisting%20of%20all%20non-empty%20subsets%20of%20vertices.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20simplicial_complex%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20r%20in%20range(1%2C%20len(vertices)%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20subset%20in%20itertools.combinations(vertices%2C%20r)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20simplicial_complex.append(list(subset))%0A%20%20%20%20%20%20%20%20return%20simplicial_complex%0A%0A%20%20%20%20def%20geometric_realization(simplex%2C%20dimension)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Perform%20geometric%20realization%20of%20a%20simplex%20into%20Euclidean%20space.%0A%20%20%20%20%20%20%20%20(Random%20placement%20for%20illustration.)%0A%20%20%20%20%20%20%20%20Mathematically%2C%20one%20should%20check%20if%20the%20resulting%20random%20points%20are%20in%20a%20general%20position%2C%20but%20we%20omit%20the%20procedure%20here.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20return%20np.random.rand(len(simplex)%2C%20dimension)%0A%0A%20%20%20%20def%20combinatorial_optimization(simplicial_complex%2C%20objective_func)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Find%20the%20simplex%20minimizing%20a%20given%20objective%20function.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20optimal_value%20%3D%20np.inf%0A%20%20%20%20%20%20%20%20optimal_solution%20%3D%20None%0A%20%20%20%20%20%20%20%20for%20simplex%20in%20simplicial_complex%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20value%20%3D%20objective_func(simplex)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20value%20%3C%20optimal_value%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20optimal_value%20%3D%20value%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20optimal_solution%20%3D%20simplex%0A%20%20%20%20%20%20%20%20return%20optimal_solution%2C%20optimal_value%0A%0A%20%20%20%20def%20dummy_objective(simplex)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Dummy%20objective%20function%3A%20minimize%20the%20size%20of%20the%20simplex.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20return%20len(simplex)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20combinatorial_optimization%2C%0A%20%20%20%20%20%20%20%20construct_simplicial_complex%2C%0A%20%20%20%20%20%20%20%20dummy_objective%2C%0A%20%20%20%20%20%20%20%20geometric_realization%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Geometric%20Realization%0A%0A%20%20%20%20An%20abstract%20simplicial%20complex%20can%20be%20embedded%20into%20Euclidean%20space%20to%20obtain%20a%20geometric%20realization.%20This%20allows%20us%20to%3A%0A%0A%20%20%20%20-%20Visualize%20simplices%20as%20actual%20geometric%20objects%20(points%2C%20edges%2C%20triangles%2C%20tetrahedra%2C%20etc)%3B%0A%20%20%20%20-%20Perform%20computations%20in%20geometry%20(e.g.%2C%20barycentric%20coordinates%2C%20volumes%2C%20embeddings).%0A%0A%20%20%20%20In%20this%20notebook%2C%20we%20perform%20a%20simple%20random%20geometric%20realization%20of%20simplices%20into%20Euclidean%20space%2C%20simply%20assigning%20random%20coordinates%20to%20each%20vertex%20for%20illustration%20purposes.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Combinatorial%20Optimization%20Example%0A%0A%20%20%20%20We%20also%20introduce%20a%20simple%20toy%20example%20of%20combinatorial%20optimization%20over%20a%20simplicial%20complex%3A%20Given%20an%20objective%20function%20(here%3A%20minimizing%20the%20size%20of%20a%20simplex)%2C%20we%20search%20for%20the%20simplex%20in%20the%20complex%20that%20minimizes%20this%20function.%20Of%20course%2C%20with%20this%20dummy%20objective%20function%2C%20the%20optimizer%20simply%20returns%20a%20%240%24-simplex%20(vertex).%0A%0A%20%20%20%20In%20more%20realistic%20settings%2C%20one%20could%20design%20much%20more%20meaningful%20objective%20functions%20depending%20on%20the%20application%20(e.g.%2C%20minimizing%20volume%2C%20maximizing%20weight%2C%20minimizing%20persistence%2C%20etc).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20combinatorial_optimization%2C%0A%20%20%20%20construct_simplicial_complex%2C%0A%20%20%20%20dummy_objective%2C%0A%20%20%20%20geometric_realization%2C%0A)%3A%0A%20%20%20%20%23%20Example%20usage%3A%0A%0A%20%20%20%20vertices%20%3D%20%5B%22A%22%2C%20%22B%22%2C%20%22C%22%2C%20%22D%22%2C%20%22E%22%5D%0A%20%20%20%20simplicial_complex%20%3D%20construct_simplicial_complex(vertices)%0A%0A%20%20%20%20optimal_solution%2C%20optimal_value%20%3D%20combinatorial_optimization(simplicial_complex%2C%20dummy_objective)%0A%0A%20%20%20%20geometric%20%3D%20geometric_realization(%5B%22A%22%2C%20%22B%22%5D%2C%202)%0A%0A%20%20%20%20print(%22Simplicial%20Complex%3A%22%2C%20simplicial_complex)%0A%20%20%20%20print(%22Optimal%20Solution%3A%22%2C%20optimal_solution)%0A%20%20%20%20print(%22Optimal%20Value%3A%22%2C%20optimal_value)%0A%20%20%20%20print(%22Geometric%20Realization%20of%20Simplex%3A%22%2C%20geometric)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A