BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20200329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20191027T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260404T015836Z
UID:5e3d5b3ef3042718171144@ist.ac.at
DTSTART:20200211T140000
DTEND:20200211T150000
DESCRIPTION:Speaker: André Lieutier\nhosted by Herbert Edelsbrunner\nAbstr
 act: This talk will consist in three parts. In the first part we will desc
 ribe algorithms for the computation of lexicographic minimal chains in an 
 abstract setting. Given a simplicial complex $K$\, we consider the problem
  of finding a simplicial $d$-chain minimal in a given homology class.This 
 is sometimes referred to as the {\\em Optimal Homologous Chain Problem} (O
 HCP).We consider here simplicial chains with coefficients in $\\Z/2 \\Z$ a
 nd the particular situation where\, given a total order on $d$-simplices$\
 \sigma_1<\\ldots<\\sigma_n$\, the weight of simplex $i$ is $2^i$. In this 
 case\,the comparison of chains is a {\\em lexicographic ordering}.Similarl
 y\, we consider the problem of {\\em finding a minimal chain for a prescri
 bed boundary}.We show that\, for both problems\, the same matrix reduction
  algorithm used for the computation of homological persistence diagrams\, 
 applied to the filtration induced by the order on $d$-simplices\, allows a
  $\\BigO(n^3)$ worst case time complexity algorithm.In the particular case
  where $K$ is a $(d+1)$-pseudo-manifold\,there is a $\\BigO(n \\log n)$ al
 gorithm which can be seen\, by duality\, as a {\\em lexicographic minimum 
 cut} in the dual graph of $K$.The second part will show how a carefully ch
 osen total order on simplices allows to retrieve regular triangulations in
  euclidean spaces\, as well as the triangulation of positive reach $2$-man
 ifolds as the support of lexicographic minimal chains.We see that each par
 t is motivated by the other.In a last part we will consider two open quest
 ions suggested by the preceding results.Results from a joined work with Da
 vid Cohen-Steiner and Julien Vuillamy.Thanks for ongoing works and discuss
 ions with:Dominique Attali\, Jean-Daniel Boissonnat\, Mathijs Wintraecken
LOCATION:Mondi Seminar Room 2\, Central Building\, ISTA
ORGANIZER:abonvent@ist.ac.at
SUMMARY:André Lieutier: Lexicographic optimal chains and manifold triangul
 ations
URL:https://talks-calendar.ista.ac.at/events/2637
END:VEVENT
END:VCALENDAR