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:20210120T004723Z
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\, IST Austria
ORGANIZER:abonvent@ist.ac.at
SUMMARY:Lexicographic optimal chains and manifold triangulations
URL:https://talks-calendar.app.ist.ac.at/events/2637
END:VEVENT
END:VCALENDAR