Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar am 14.12.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 21.12.2017 Helmut Alt zum Thema: Für manche Kunstgalerien lohnen sich irrationale Wächter *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 19.12.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 7.11.2017, 12 Uhr, SR 130 (Arnimallee 3) Jonas Cleve zum Thema: The Length of the Beacon Attraction Trajectory ================================================================== Subject: Mittagsseminar am 14.12.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 14.12.2017 Boris Klemz zum Thema: Paired Approximation Problems *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar 12.12.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 12.12.2017, 12 Uhr, SR 130 (Arnimallee 3) Max Willert zum Thema: Stabbing Disks and LP-type problems ================================================================== Subject: Fwd: [all] Einladung zur Verteidigung meiner Bachelorarbeit Tomorrow. -------- Forwarded Message -------- Subject: [all] Einladung zur Verteidigung meiner Bachelorarbeit Liebe Institutsangeh=F6rige, hiermit m=F6chte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit = mit dem Titel "Fast dynamic planar convex set maintenance using finger trees"= einladen. Die Verteidigung findet am Dienstag, 5. Dezember, um 12:15 Uhr in der Arnimallee 3, SR 130 statt. Betreut wurde die Arbeit von Prof. Dr.= Wolfgang Mulzer. Abstract: Let a convex set in the plane be given by either a set of points or half-spaces. The maintenance of it under insertion and deletion of elements is a fundamental problem in computational geometry. This thesis considers a data-structure which solves this problem. It was drafted by the researchers Kaplan, Tarjan and Tsioutsiouliklis in a paper about kinetic heaps (priority queues with linear functions as keys rather than fixed values). However it was never written down in detail. We state thei= r construction explicitly. Its foundation is built by a deletion-only structure which uses finger trees (height balanced trees with preferred access points) to represent convex sets. With the semi-dynamic structure at hand, a fully dynamic one may be constructed using given dynamization transformations. The binary counting scheme transformation of Bentley and= Saxe yields an insertion-and-deletion structure with $O(\log^2 n)$ worst-case vertical ray query time, $O(\log n)$ amortized insertion time and $O(\log n \log \log n)$ amortized deletion time. A transformation of Brodal and Jacob results in a structure with $O(\log n)$ worst-case vertical ray query time, $O(\log n \log \log \log n)$ amortized insertion= and $O(\log n \log \log n)$ amortized deletion time. Viele Gr=FC=DFe, Chris Hofer ================================================================== Subject: Mittagsseminar am Donnerstag 30.11.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am    Donnerstag, 30.11.2017 Günter Rote über Kallus’s linear-time algorithm for the largest triangle in a convex polygon *************************************************** Ort: Takustraße 9, Seminarraum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar 28.11.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 28.11.2017, 12:00 Uhr s.t. Bahareh Banyassady zum Thema: Point location via violator spaces ************************************* ================================================================== Subject: Mittagsseminar 28.11.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 28.11.2017, 12:00 Uhr s.t. Bahareh Banyassady zum Thema: Point location via violator spaces ************************************* ================================================================== Subject: Mittagsseminar 21. 11. und 23. 11. Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 21.11.2017, 12 Uhr, A3, SR 130 Frank Hoffmann zum Thema: Two Art Gallery Results for Orthogonal Simple Polygons und am Donnerstag, 23.11.2017, 12 Uhr, SR 055 Claudia Dieckmann zum Thema: Voronoi Diagram in the Laguerre Geometry and its Applications ================================================================== Subject: Mittagsseminar 14.11. und 16.11.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 13.11.2017, 12 Uhr, A3, SR 130 Katharina Klost zum Thema: L. Stacho's proof for stabbing disks with 5 points und am Donnerstag, 16.11.2017, 12 Uhr, SR 055 Nadja Scharf zum Thema: Online Square-into-Dynamic-Square Packing ================================================================== Subject: Mittagsseminar am 7. und 9.11.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 7.11.2017, 12 Uhr, SR 055 Jonas Cleve zum Thema: Covering Orthotrees with Beacons und am Donnerstag, 9.11.2017, 12 Uhr, SR 055 Max Willert zum Thema: Cops, Robbers and Doughnuts ================================================================== Subject: Mittagsseminar am 02.11.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 02.11.2017 Boris Klemz zum Thema: Non-Crossing Connectors in Pseudodisks and an Application: the Tube Problem *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar 24. und 26.10.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 24.10.2017, 12:00 Uhr s.t., SR 055 Helmut Alt zum Thema: Not all bierdeckels can fit in a finite finite container simultaneously und am Donnerstag, 26.10.2017, 12:00 Uhr s.t., SR 055 Günter Rote zum Thema: Simulation of nondeterministic Turing machines ================================================================== Subject: Mittagsseminar 17. und 19.10.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 17.10.2017, 12 Uhr, SR 055 Astrid Sturm zum Thema: Bayesian Networks, Decision Graphs and the ClimeFish project Donnerstag, 19.10.2017, 12 Uhr, SR 055 Wolfgang Mulzer zum Thema: Cap sets and the rank miracle ================================================================== Subject: Miitagsseminar am 12.10.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 12.10.2017 Klaus Kriegel zum Thema: Bisecting masses with two cuts *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar 05.10.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 05. 10. 2017 Bahareh Banyassady zum Thema: Palanar Directed Reachability Problem. *************************************************** Ort: Takustra=C3=9Fe 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. (vielleicht 11:45 s.t!) ================================================================== Subject: Mittagsseminar am 21.09 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 21.09.2017 Boris Klemz zum Thema: Disk Obedient Drawings *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar 19.9.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am         Dienstag, 14.9.2017, 12 Uh, SR 055         Katharina Klost         zum Thema: Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time ================================================================== Subject: Mittagsseminar 14.9.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 14.9.2017, 12 Uhr, SR 055 Claudia Dieckmann zum Thema:The Painter's Problem: covering a grid with colored connected polygons ================================================================== Subject: Mittagsseminar 12.9.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 12.09.2017, 12 Uhr, SR 055 Max Willert zum Thema: The joy of SET ================================================================== Subject: Mittagsseminar 5.9. + 7.9.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 5.9.2017, 12 Uhr, SR 055 Max Willert zum Thema: Comparison Decision Trees und Donnerstag, 7.9.2017, 12 Uhr, SR 055 Frank Hoffmann zum Thema: Collaborative Grid Searching ================================================================== Subject: Mittagsseminar am 25.07.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 24.07.2017 Wolfgang Mulzer zum Thema: Covering Planar Graphs with a Fixed Number of Balls *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 22.08.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 22.08.2017 Nadja Scharf zum Thema: Packing Disks in 3D *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** --=20 Nadja Scharf Freie Universit=C3=A4t Berlin Institut f=C3=BCr Informatik AG Theoretische Informatik Takustra=C3=9Fe 9, Raum 122 14195 Berlin ================================================================== Subject: Mittagsseminar 10.8 und 15.8 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 10. 8. 2017 Bahareh Banyassady zum Thema: General Sequential Time-Space Tradeoff for Finding Unique Elements und am Dienstag, 15. 8. 2017 Günter Rote zum Thema: Majority colorings *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar (10.08 und 15.08) Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 10. 8. 2017 Bahareh Banyassady zum Thema: General Sequential Time-Space Tradeoff for Finding Unique Elements. und am Dienstag, 15. 8. 2017 Günter Rote zum Thema: Majority colorings *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar (10.08 und 15.08) Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 10. 8. 2017 Bahareh Banyassady zum Thema: General Sequential Time-Space Tradeoff for Finding Unique Elements. und am Dienstag, 15. 8. 2017 G=C3=BCnter Rote zum Thema: Majority colorings *************************************************** Ort: Takustra=C3=9Fe 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Fwd: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarbeit und um 12 -------- Forwarded Message -------- Subject: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarb= eit Date: Fri, 4 Aug 2017 13:42:33 +0200 From: "Tobias Gro=C3=9F" To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de Sehr geehrte Damen und Herren, hiermit m=C3=B6chte ich Sie herzlich zur Verteidigung meiner Bachelorarbe= it mit dem Titel "Algorithmen und Anwendungen f=C3=BCr das Triangle Scheduling Problem" einladen. Die Verteidigung findet am 08.08.2017 um 12 Uhr s.t. i= m Raum 055 in der Takustra=C3=9Fe 9 statt. Die Arbeit wurde von Dr. Claudia= Dieckmann betreut. Zusammenfassung: Das Triangle Scheduling Problem, von D=C3=BCrr u.a. in [1] vorgestellt, i= st ein Spezialfall von Mixed-criticility Scheduling mit Jobs in Form gleichschenkliger Dreiecke. Da es NP-schwer ist, kann der optimale Zeitplan im Allgemeinen nur mittels Brute-Force-Algorithmus gefunden werden, unter der Annahme P=E2=89=A0NP. Der effiziente gierige Ansatz, jeweils das gr=C3=B6=C3=9Fte Dreieck in di= e gr=C3=B6=C3=9Fte L=C3=BCcke im Zeitplan zu setzen, kann in vielen F=C3=A4llen die optimale= L=C3=B6sung ermitteln, wie quantitative Tests mit gleich verteilt zuf=C3=A4lligen Job= gr=C3=B6=C3=9Fen zeigen. An den wenigen Beispielen mit nicht optimalem Ergebnis kann man untersuchen, wann der gierige Algorithmus die falsche Entscheidung trifft= =2E Dar=C3=BCber hinaus kann mit Hilfe dynamischer Programmierung eine (1+=CE=B5)-Approximation des optimalen Zeitplans gefunden werden. Indem d= ie Jobgr=C3=B6=C3=9Fen und Startzeiten vorher aufgerundet werden, reduziert = sich die L=C3=B6sung dabei auf die L=C3=B6sung von O(n^log(n)) vielen Teilprobleme= n. In dieser Arbeit entwerfe ich die drei Algorithmen in Pseudocode und implementiere sie in der Programmiersprache Java. Au=C3=9Ferdem ist das Triangle Scheduling Problem geometrisch betrachtet = ein Spezialfall des Packungsproblems in einem Rechteck und ich verallgemeiner= e den Brute-Force-Algorithmus auf andere Figuren wie gleichseitige Dreiecke= , Kreise etc. Mit freundlichen Gr=C3=BC=C3=9Fen Tobias Gro=C3=9F [1] C. D=C3=BCrr, Z. Hanz=C3=A1lek, C. Konrad, R. Sitters, O. C. V=C3=A1s= quez, and G. J. Woeginger, =E2=80=9CThe triangle scheduling problem,=E2=80=9D CoRR, vol. = abs/1602.04365, 2016. [Online]. Available: http://arxiv.org/abs/1602.04365 ================================================================== Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit Um 11. -------- Forwarded Message -------- Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit Date: Fri, 4 Aug 2017 13:32:31 +0200 From: Jakob K=F6hler To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-studi@inf.fu-berlin.de, Zentiks, Sera Renee , Sch=FCler, Diana Sehr geehrte Damen und Herren, hiermit lade ich Sie zur Verteidigung meiner Bachelorarbeit mit dem Titel "Optimale Orientierung eines 3D-Modells f=FCr den Metalldruck" ein.= Die Pr=E4sentation findet am Di. 08.08.17, 11 Uhr s.t., im SR 055 der Takustra=DFe 9 statt. Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut. Zweitgutachter ist PD Dr. rer. nat. Klaus Kriegel. Zusammenfassung: Beim 3D-Druck dient die St=FCtzstruktur der Stabilisierung des Modells w=E4hrend des Druckprozesses. Da die St=FCtzstruktur das Modell von unten= abst=FCtzt, wirkt sich dessen Orientierung im Raum stark auf das Volumen der notwendigen St=FCtzstruktur aus. Es l=E4sst sich zeigen, dass das Problem der optimalen Orientierung eines 3D-Modells unter diesem Gesichtspunkt in polynomieller Zeit l=F6sbar ist. Desweiteren wird ein approximativer Algoritumus vorgestellt, welcher das Problem f=FCr konvexe= Modelle in linearer Zeit l=F6st. In modifizierter Form l=E4sst sich der Algorithmus auch auf nicht-konvexe Modelle anwenden, was allerdings in einer quadratischen Laufzeit resultiert. In der Auswertung zeigt sich, dass durch Anwendung des Algorithmus auf bestimmte Modelle signifikante Einsparungen in den Materialkosten erzielt werden k=F6nnen. Mit freundlichen Gr=FC=DFen Jakob K=F6hler ================================================================== Subject: Mittagsseminar am 27. Juli 2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 27.7.2017 Tillmann Miltzow zum Thema: Is area universality ∀∃R-complete? (forall-exists-Ⓡeals-complete) (joint work with Michael G. Dobbins, Linda Kleist, Paweł Rzążewski) *************************************************** Ort: Takustr. 9, Seminarraum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 25.07.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 25.07.2017 Wolfgang Mulzer zum Thema: Yet another proof of Chernoff's bound *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 20.07.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 20.07.2017, 12 Uhr, SR 055 Katharina Klost zum Thema: Weighted girth in directed planar graphs ================================================================== Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar am 18.07.2017 "das Wenden" On 18.07.2017 10:21, Helmut Alt wrote: >> Im Rahmen des Mittagsseminars der >> Theoretischen Informatik der FU Berlin >> spricht am >> >> Dienstag, 18.07.2017 >> Helmut Alt >> zum Thema: >> Über das Weneden eines konvexen Vielecks in einem ebensolchen >> >> *************************************************** >> Ort: Takustr. 9, RM 055 >> >> Uhrzeit: 12 Uhr s.t. >> *************************************************** >> ================================================================== Subject: Mittagsseminar am 18.07.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 18.07.2017 Helmut Alt zum Thema: Über das Weneden eines konvexen Vielecks in einem ebensolchen *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar, 6.7.17 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 6. 7. 2017, 12:00 Uhr s.t., SR 055 Claudia Dieckmann zum Thema: Maximum-Area Triangle in a Convex Polygon ================================================================== Subject: Fwd: Einladung zur Verteidigung meiner Bachelorarbeit Mittagsseminar morgen. -------- Forwarded Message -------- Subject: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarbeit Sehr geehrte Damen und Herren, hiermit lade ich Sie herzlich zur Verteidigung meiner Bachelorarbeit mit dem Titel "Jump Point Search auf verallgemeinerten Spielbrettern" ein. Die Verteidigung findet am Dienstag, den 4.7.2017, um 12:00 Uhr im Raum 055 in der Takustra=C3=9Fe 9 statt. Die Gutachter sind Prof. Dr. Wolfgang Mulzer und Dr. Claudia Dieckmann. Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut. Abstrakt der Arbeit: Jump Point Search (kurz JPS) ist ein neuer Algorithmus in der Wegfindung.= Durch seine herausragenden Performance findet er, vor allem in der Spiele-Entwicklung, viel Anwendung. Leider beschr=C3=A4nkt sich die Definition dieses Algorithmus' auf quadratische Gitter. Meine Arbeit besch=C3=A4ftigte sich mit der Idee den Anwendungsbereich de= s JPS zu erweitern. Hierf=C3=BCr abstrahierte und mathematisierte ich sowohl seine Entwicklun= g, als auch seine Handlungsweise, adaptierte dieses Konzept auf regelm=C3=A4=C3=9Fige Dreiecks-tesselierte = Fl=C3=A4chen und arbeitete die Kriterien f=C3=BCr eine Verallgemeinerung heraus. Den entstandenen Algorithmus analysierte ich stochastisch und testete ihn gegen den "Jack of all trades"-Pathfinder A*. Mit freundlichen Gr=C3=BC=C3=9Fen Felix Wiener ================================================================== Subject: Mittagsseminar heute 29. 6. 2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 29. 6. 2017, 12:00 Uhr s.t., SR 055 Günter Rote zum Thema: Stable matching in a grid ================================================================== Subject: Mittagsseminar 20.+22.06.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 20.06.2017, 12 Uhr, SR 055 Frank Hoffmann zum Thema: Two classical graph coloring results und Donnerstag, 22.06.2017, 12 Uhr, SR 055 Max Willert zum Thema: Distributed algorithm for maximal independet set ================================================================== Subject: Mittagsseminar am 15.06.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 15.06.2017 Bahareh Banyassady zum Thema: A simple analysis of Rabin's algorithm for finding closest pairs *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 13.06.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 13.06.2017 Edouard Bonnet zum Thema: subexponential algorithms in non sparse classes of graphs *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 08.06.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 08.06.2017 Wolfgang Mulzer zum Thema: Joints and the Polynomial Method *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar 6.6. 2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 6.6.2017 Katharina Klost zum Thema: Happy edge and vertex colorings *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. ================================================================== Subject: Mittagsseminar 30.5. und 1.6.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 30. 5. 2017 Günter Rote zum Thema: Multidimensional divide and conquer: closest pairs und am Donnerstag, 1. 6. 2017 Klaus Kriegel zum Thema: Closed meanders *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. ================================================================== Subject: Mittagsseminar 18. und 23.05.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 18.05.2017, 12 Uhr, SR 055 Wolfgang Mulzer zum Thema: Adaptive Point Location in Planar Convex Subdivisions Dienstag, 23.05.2017, 12 Uhr, SR 055 Katinka Wolter zum Thema: Swimming with Fishes and Sharks: Beneath the Surface of Queue-based Ethereum Mining Pools ================================================================== Subject: Mittagsseminar 16.05.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 16.05.2017, 12 Uhr, SR 055 Max Willert zum Thema: The Ice-cream Lemma ================================================================== Subject: Mittagsseminar am 09. und 11.05.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 09.05.2017 Boris Klemz zum Thema: Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings und am Donnerstag, 11.05.2017 Frank Hoffmann zum Thema: The proper orientation number of undirected graphs *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 4.5.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 4.5.2017 Bahareh Banyassady zum Thema: Find an area maximizing triangle inscribed in a given convex polygon *************************************************** Ort: Takustra=C3=9Fe 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. ================================================================== Subject: Mittagsseminar am 2.5.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 2.5.2017 Katharina Klost zum Thema: Intersections of regular polygons with pairwise excluded centers *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 25. und 27. 4. 2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 25. 4. 2017 Günter Rote zum Thema: Maximum induced matchings in convex bipartite graphs und am Donnerstag, 27. 4. 2017 Frank Hoffmann zum Thema: The proper orientation number of undirected graphs *************************************************** Ort: Takustraße 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar 20.4.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 20.04.2017, 12 Uhr, SR 055 Claudia Dieckmann zum Thema: The triangle scheduling problem ================================================================== Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner Masterarbeit -------- Forwarded Message -------- Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit Date: Tue, 28 Mar 2017 11:23:05 +0200 From: Jonas Cleve To: i-prof@inf.fu-berlin.de, i-wimi@inf.fu-berlin.de, i-studi@inf.fu-berlin.de CC: diana.schueler@fu-berlin.de, SeraRenee.Zentiks@fu-berlin.de Sehr geehrte Damen und Herren, hiermit lade ich Sie zur Verteidigung meiner Masterarbeit mit dem Titel =E2=80=9ECombinatorics of Beacon-based Routing and Guarding in Three Dime= nsions=E2=80=9C ein. Die Pr=C3=A4sentation findet am Donnerstag, den 30.03.2017 um 12:00 s.t. im Raum SR 055 im Rahmen des Mittagsseminars der Theoretischen Informatik statt. Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitgutachter ist Dr. Frank Hoffmann. Mit freundlichen Gr=C3=BC=C3=9Fen Jonas Cleve *Abstract:* A beacon is a point-like object which can be enabled to exert a magnetic pull on other point-like objects in space. Those objects then move towards the beacon in a greedy fashion until they are either stuck at an obstacle or reach the beacon's location. Beacons placed inside three-dimensional polytopes can be used to route point-like objects from one location to another. A second use case is to cover a polytope such that every point-like object at an arbitrary location in the polytope can reach at least one of the beacons once the latter is activated. The topic of beacon-based routing and guarding was introduced by Biro et al. [2] in 2011 and covered in detail by Biro in his PhD thesis [1]. Therein various aspects of beacons in the polygonal domain of two dimensions were studied. In this thesis we provide the first results for beacon-based routing and guarding for three dimensions. We first define the setting for three dimensions and look at two-dimensional beacon-based routing which lays the groundwork for our three-dimensional approach. We then have a look at the complexity of certain three-dimensional routing and guarding problems for which a smallest set of beacons should be obtained. We show that some of the problems are at least as hard as their two-dimensional counterpart which makes them NP-hard and APX-hard. For the problem of finding a smallest set of beacons to be able to route between any pair of points in a polytope we show that it is always sufficient and sometimes necessary to place floor((m+1)/3) beacons, where m is the number of tetrahedra in a tetrahedral decomposition of the polytope. Finally, we show that there exists a polytope which cannot be covered by placing a beacon at each vertex of the polytope. [1] Michael Biro. =E2=80=9CBeacon-Based Routing and Guarding=E2=80=9D. Ph= D thesis. State University of New York at Stony Brook, 2013. [2] Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. =E2=80=9CBeacon-Based Routing and Coverage=E2=80=9D. In: = 21st Fall Workshop on Computational Geometry (FWCG 2011). 2011. ================================================================== Subject: Mittagsseminar 28.03.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 28.03.2017, 12 Uhr, SR 053 (!) Wolfgang Mulzer zum Thema: Growing Prioritized Disks and Rectangles ================================================================== Subject: Mittagsseminar 28.03.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 28.03.2017, 12 Uhr, SR 055 Frank Hoffmann zum Thema: The proper orientation number of undirected graphs ================================================================== Subject: Mittagsseminar am 21. und 23. 3. 2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 21. 3. 2017 G=C3=BCnter Rote zum Thema: Audioactive decay and the Conway sequence 1, 11, 21, 1211, 111221, 312211, 13112221, .... und am Donnerstag, 23. 3. 2017 Max Willert zum Thema: Deformable Spanners *************************************************** Ort: Takustra=C3=9Fe 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner Masterarbeit -------- Forwarded Message -------- Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit Date: Tue, 14 Mar 2017 16:03:13 +0100 From: Katharina Klost To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-studi@inf.fu-berlin.de CC: renee.zentiks@fu-berlin.de Sehr geehrte Damen und Herren, hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit dem Titel "Complexity of recognizing generalized transmission graphs" ein= =2E Die Pr=C3=A4sentation findet am Donnerstag, den 16.03.2017 um 12:00 s.t. = im Rahmen des Mittagssemiars f=C3=BCr Theoretische Informatik in SR 055 stat= t. Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitkorrektor ist PD Dr. Klaus Kriegel Mit freundlichen Gr=C3=BC=C3=9Fen Katharina Klost *Zusammenfassung:* Der allgemeine Transmissionsgraph einer Menge von geometrischen Objekten, mit einem ausgezeichneten Punkt f=C3=BCr jedes Element der Men= ge, hat einen Knoten pro Element und eine gerichtete Kante /(u,v)/ genau dann wenn der Punkt von /v/ in /u/ liegt. Diese Graphen sind ein m=C3=B6gliches Modell f=C3=BCr Erreichbarkeit von Antennen. Die Komplexit=C3=A4tsklasse ETR enth=C3=A4lt alle Sprachen, die in Polyno= mialzeit auf einen Satz der Form /=E2=88=83x_1,.,x_n:=CF=95(x_1,..., x_n) / reduzi= ert werden k=C3=B6nnen. Hierbei stammen/x_1,..., x_n/ aus den reelen Zahlen. Es ist bekannt, dass ETR zwischen NP und PSPACE liegt. F=C3=BCr viele geometrische Entscheidungsprobleme, wie zum Beispiel das Erkennen von Kreisgraphen und Schnittgraphen von Strecken ist bekannt, dass diese ETR-vollst=C3=A4ndig sind. In dieser Arbeit werden /allgemeine Transmissionsgraphen/ formal definiert und es wird gezeigt, dass das Erkennen von allgemeinen Transmissionsgraphen von k-Kugeln, regelm=C3=A4=C3=9Figen Polygonen, Stre= cken und Kreissektoren ETR-vollst=C3=A4ndig ist. *Abstract:* Given an arrangement of geometric objects with one point of each object singled out. The generalized transmission graph of this arrangement consists of one vertex per element and a directed edge /(u,v)/ if and only if the point of /v/ lies in /u/. These graphs can serve as a generalized model of antenna reachability. The complexity class ETR contains all problems that are polynomial time reducible to a sentence of the form /=E2=88=83x_1,.,x_n:=CF=95(x_1,..., x= _n)/ where /x_1,..., x_n/ are interpreted over the real numbers. It aims to capture the complexity of the existential theory of the reals. It is well known that ETR lies between NP and PSPACE. For many geometric decision problems, such as recognition of disk graphs and of intersection graphs of lines, it is known that they are complete for ETR. In this thesis we formally introduce the class of /generalized transmission graphs/ and show that the recognition problem of generalized transmission graphs of k-spheres, regular polygons, line segments and circular sectors is complete for the complexity class ETR. ================================================================== Subject: Mittagsseminar 14.03.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 14.03.2017, 12 Uhr, SR 055 Nadja Scharf zum Thema: =20 Symmetric Assembly Puzzles=20 --=20 Nadja Scharf Freie Universit=C3=A4t Berlin Institut f=C3=BCr Informatik AG Theoretische Informatik Takustra=C3=9Fe 9, Raum 122 14195 Berlin ================================================================== Subject: Mittagsseminar am 28.02. und am 02.03.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 28.02.2017, 12 Uhr, SR 053 (Achtung: nicht 055) Florian Hartmann zum Thema: Computing Graph-Theoretic Similarity Scores Efficiently (Verteidigung der Bachelorarbeit) und am Donnerstag, 02.03.2017, 12 Uhr, SR 055 Klaus Kriegel zum Thema: Rainbow Meanders an Cartesian Billiards ================================================================== Subject: Mittagsseminar morgen Donnerstag, 23.02.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 23.02.2017, 12 Uhr, SR 055 G=FCnter Rote zum Thema: Guess your own number! and Steiner triple systems! ================================================================== Subject: Fwd: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarbeit Tomorrow. -------- Forwarded Message -------- Subject: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarb= eit Date: Tue, 7 Feb 2017 10:13:53 +0100 From: Miro Baeten To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-studi@inf.fu-berlin.de, Ren=E9e Zentiks Sehr geehrte Damen und Herren, hiermit m=F6chte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit = mit dem Titel "Erstellung eines GLL-Parsergenerators f=FCr kontextfreie Grammatiken" einladen. Die Arbeit entstand in der AG Theoretische Informatik und wurde von Herrn Prof. Dr. Wolfgang Mulzer betreut. Zweitgutachter ist Herr Prof. Dr. Helmut Alt. Die Verteidigung findet am Dienstag, den 14.02.2017 um 12:00 s.t. im Seminarraum 055 in der Takustra=DFe 9 statt. Mit freundlichen Gr=FC=DFen Miro Baeten Zusammenfassung: Die Arbeit besch=E4ftigt sich mit der Erstellung eines Parsergenerators f= =FCr allgemeine kontextfreie Grammatiken unter Verwendung des GLL-Algorithmus,= welcher mit ambigen Grammatiken in O(n^3) umzugehen wei=DF. Sein Einsatz bietet sich unter anderem in der Computerlinguistik, dem Software Reengineering und in Compilern an. Die Laufzeit wird durch die Verwendung von als Graph= en strukturierten Stacks (GSS) sowie einem Shared Packed Parse Forest (SPPF)= erreicht, der mehrerer valide Ableitungen zusammenfasst. Zun=E4chst wird auf den Algorithmus, danach auf den Generator und die Parser eingegangen. Der Generator abstrahiert die Grammatiken in einem Modell, analysiert dieses und erzeug= t daraus einen Parser, der sich an die asymptotische Laufzeit des Algorithm= us h=E4lt. Damit die Parser ambige Grammatiken schneller ableiten k=F6nnen, wird der Algorithmus um eine Parallelisierung erweitert. Abschlie=DFend wird beleuchtet, wie der Parsergenerator in Zukunft ausgebaut werden kann. Bedeutend ist sowohl der weitere Umgang mit den SPPFs als auch die Verbesserung des GSS. ================================================================== Subject: Mittagsseminar 02.02.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 02.02.2017, 12 Uhr, SR 055 Max Willert zum Thema: Subset-Sum ... most probably ================================================================== Subject: Mittagsseminar 26.01.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 26.01.2017, 12 Uhr, SR 055 Nadja Scharf zum Thema: =20 A PTAS for the Square Packing Problem =20 --=20 Nadja Scharf Freie Universit=C3=A4t Berlin Institut f=C3=BCr Informatik AG Theoretische Informatik Takustra=C3=9Fe 9, Raum 122 14195 Berlin ================================================================== Subject: Mittagsseminar 24.01.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 24.01.2017, 12 Uhr, SR 055 Frank Hoffmann zum Thema: Dominance in colored stochastic point sets ================================================================== Subject: Mittagsseminar heute, 17.1.2017: The (Prouhet-)Tarry-Escott Problem Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 17.1.2017, 12 Uhr, SR 055 G=FCnter Rote zum Thema: The Prouhet-Tarry-Escott problem about annihilation of= polynomials ================================================================== Subject: Mittagsseminar am 12.01.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 12.01.2017 Wolfgang Mulzer zum Thema: Stabbing Pairwise Intersecting Disks with Five Points *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar heute, 19.01.2017 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht heute, Dienstag, 19.01.2017 Bahareh Banyassady zum Thema: Higher-Order Voronoi Diagrams in Constrained memory model. *************************************************** *Ort: Takustr. 9, SR 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar heute, 5.1.2017: Plane graph isomorphism Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 5.1.2017, 12 Uhr, SR 055 G=FCnter Rote zum Thema: Plane graph isomorphism testing ================================================================== Subject: Mittagsseminar TI Dienstag, 02.01.17 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 03.01.2017 Boris Klemz zum Thema: Ordered Level Planarity *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ==================================================================