{"id":1489,"date":"2024-08-13T14:26:46","date_gmt":"2024-08-13T14:26:46","guid":{"rendered":"https:\/\/summergeometry.org\/sgi2024\/?p=1489"},"modified":"2024-08-13T14:26:47","modified_gmt":"2024-08-13T14:26:47","slug":"voronoi-tessellations","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2024\/voronoi-tessellations\/","title":{"rendered":"Voronoi Tessellations"},"content":{"rendered":"\n

Last week, we looked into Voronoi tessellations and their potential for high dimensional sampling and integral approximations. <\/p>\n\n\n\n

When we have a very complicated high-dimensional function, it can be very challenging to compute its integral in a given domain. A standard way to approximate it is through Monte Carlo integration<\/p>\n\n\n\n

Monte Carlo integration<\/h2>\n\n\n\n

Monte Carlo integration is a technique consisting of querying the integrand function f<\/em> at N<\/em> random <\/strong>locations uniformly<\/strong>, taking the average, and then multiplying the region’s volume:<\/p>\n\n\n\n

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

The law of large numbers ensures that, in the limit, this quantity approximates the actual integral better and better.<\/p>\n\n\n\n

Okay, but<\/strong> the points are sampled i.i.d. uniformly, which might not be optimal to compute the integral’s value from a very small sample size. Maybe we can find a way to guide<\/em> the sampling and leverage prior knowledge we might have about the sample space.
Okay, and<\/strong> maybe the points are not extracted i.i.d. What if we have no control over the function – maybe it’s some very big machine in a distant factory, or an event occurring once in a decade. If we can’t ensure that the points are i.i.d. we just can’t use Monte Carlo integration. <\/p>\n\n\n\n

Therefore, we will investigate whether we can use Voronoi tessellations to overcome this limitation.<\/p>\n\n\n\n

Voronoi Tessellation<\/h2>\n\n\n\n

A Voronoi tessellation is a partition of the space according to the following rules:<\/p>\n\n\n\n

    \n
  • We start with some “pivot” points pi<\/sub><\/em> in the space (which could be the points at which we evaluate the integrand function)<\/li>\n<\/ul>\n\n\n
    \n
    \"\"<\/figure>\n<\/div>\n\n\n
      \n
    • Now, we create as many regions as there are initial pivot points defined as follows: a point x<\/em> in the space belongs to the region of the point pi<\/sub><\/em><\/em> if the point pi<\/sub><\/em> is the closest pivotal point to x<\/em> :<\/li>\n<\/ul>\n\n\n
      \n
      \"\"<\/figure>\n<\/div>\n\n\n
      \n

      Voronoi tessellation is essentially one iteration of k-means clustering where the centroids are the pivotal points pi<\/sub><\/em> and the data to cluster are all the points x<\/em> in the domain<\/p>\n<\/blockquote>\n\n\n\n

      Some immediate ideas here:<\/p>\n\n\n\n

        \n
      • We can immediately try out “Voronoi integration”, where we multiply the value of the integrand at each starting point f(pi<\/sub>)<\/em> by the volume of its corresponding region, summing them all up, and see how it behaves compared to Monte Carlo integration (especially in high dimensions)<\/li>\n\n\n\n
      • We can exploit Bayesian optimisation to guide the sampling of the points pi<\/sub><\/em> as we don’t require them to be i.i.d. unlike Monte Carlo integration<\/li>\n\n\n\n
      • We can exploit prior knowledge on the integration domain to weight the areas by a measure<\/em><\/li>\n<\/ul>\n\n\n\n


        In the next blog posts, we will see some of these ideas in action!<\/p>\n","protected":false},"excerpt":{"rendered":"

        Last week, we looked into Voronoi tessellations and their potential for high dimensional sampling and integral approximations. When we have a very complicated high-dimensional function, it can be very challenging to compute its integral in a given domain. A standard way to approximate it is through Monte Carlo integration Monte Carlo integration Monte Carlo integration […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[40],"tags":[79,80,78],"ppma_author":[13],"class_list":["post-1489","post","type-post","status-publish","format-standard","hentry","category-math","tag-integration","tag-monte-carlo","tag-voronoi"],"authors":[{"term_id":13,"user_id":0,"is_guest":1,"slug":"cap-riccardo-ali-it","display_name":"riccardo.ali.it","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""}],"_links":{"self":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/1489","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/comments?post=1489"}],"version-history":[{"count":1,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/1489\/revisions"}],"predecessor-version":[{"id":1493,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/1489\/revisions\/1493"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/media?parent=1489"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/categories?post=1489"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/tags?post=1489"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/ppma_author?post=1489"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}