Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, October 14, 2014, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Matias Korman (National Institute of Informatics Tokyo)

Computing extremal distances in polygonal domains

The geodesic distance between two points p,q in a polygonal domain P is defined as the path of shortest length connecting the two points that contained in P. This distance is a proper metric, and as such the usual concepts of diameter (i.e., points of P that are furthest away) and center (i.e., point whose distance to its furthest away point is minimized) naturally extend. Although computing these traits in simple domains (i.e., domains without holes) is easy, the same does not hold when holes are present in the domain. In this talk we discuss the difficulties that lie in designing algorithms for computing the center and diameter, and how to work around them so as to obtain algorithms that run in polynomial time.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login