Technische Universität Braunschweig
  • Studium & Lehre
    • Vor dem Studium
      • Informationen für Studieninteressierte
      • Studiengänge von A-Z
      • Bewerbung
      • Warum die TU?
    • Im Studium
      • Erstsemester-Hub
      • Semestertermine
      • Lehrveranstaltungen und Qualifikationen
      • Studienorganisation
      • Beratungsnavi
      • Finanzierung und Kosten
      • Besondere Studienbedingungen
      • Gesundheit & Wohlbefinden
      • Studentisches Engagement
    • Nach dem Studium
      • Career Service
      • Alumni*ae
      • Exmatrikulation und Vorbeglaubigung
      • Nach dem Abschluss
    • Strategien und Qualitätsmanagement
      • Qualitätsmanagement
      • Studienqualitätsmittel
      • TU Lehrpreis
    • Für Lehrende
      • Informationen für Lehrende
      • Konzepte
      • Lernmanagementsystem Stud.IP
      • Impact Learning
    • Kontakt
      • Studienservice-Center
      • Sag's uns: Ideen‑ & Beschwerdestelle Studium & Lehre
      • Zentrale Studienberatung
      • Immatrikulationsamt
      • Abteilung 16 - Studium und Lehre
      • Career Service
      • Projekthaus
  • Forschung
    • Forschungsprofil
      • Forschungsschwerpunkte
      • Exzellenzcluster der TU Braunschweig
      • Forschungsprojekte
      • Forschungszentren
      • Forschungsprofile der Professuren
    • Frühe Karrierephase
      • Förderung in den frühen Phasen der wissenschaftlichen Karriere
      • Promotion
      • Postdocs
      • Nachwuchsgruppenleitung
      • Junior Professur und Tenure-Track
      • Habilitation
      • Service-Angebote für Wissenschaftler*innen
    • Forschungsdaten & Transparenz
      • Transparenz in der Forschung
      • Forschungsdaten
      • Open Access Strategie
    • Forschungsförderung
      • Netzwerk Forschungsförderung
      • Datenbanken und Stiftungen
    • Kontakt
      • Forschungsservice
      • Graduiertenakademie
      • Organisation wissenschaftlicher Veranstaltungen
  • Transfer
    • Transferprofil
      • Transferstrategie "TIES® with Impact"
      • Technologietransfer
      • Wissenstransfer
      • Relationship Management
      • Transferprojekte
    • Innovation
      • Startups
      • Patente
      • Impact Map
    • Schule-Uni-Angebote
      • Webportal für Schule-Uni-Aktivitäten
      • Kinder-Uni Vorlesungen
      • Kinder-Uni Podcast
      • LeoLabs – Campuslabore für Schüler*innen
      • LeoVan – Mobile Experimente für Schulen
      • School Outreach Fonds
      • Hochschulinformationstag
    • Für Unternehmen
      • Deutschlandstipendium
      • Freunde & Förderer
    • Für Alumni*ae
      • Dem Netzwerk beitreten
      • Alumni*ae kennen lernen
      • Alumni*ae Talks
      • Campustouren
    • Für alle
      • Community Café
      • Community Podcast
      • Uni-Shop
  • International
    • Internationale Studierende
      • Warum Braunschweig?
      • Studium mit Abschluss
      • Austauschstudium
      • TU Braunschweig Summer School
      • Schüler*innen von deutschen Auslandsschulen
      • Geflüchtete
      • International Student Support
      • International Career Service
    • Wege ins Ausland
      • Studium im Ausland
      • Praktikum im Ausland
      • Lehren und Forschen im Ausland
      • Arbeiten im Ausland
    • Internationale Forschende
      • Welcome Support for International Researchers
      • Service für gastgebende Einrichtungen
    • Sprachen und interkulturelle Kompetenzvermittlung
      • Deutsch lernen
      • Fremdsprachen lernen
      • Interkulturelle Kompetenzvermittlung
    • Internationales Profil
      • Internationalisierung
      • Internationale Kooperationen
      • Strategische Partnerschaften
      • Internationale Netzwerke
    • International House
      • Wir über uns
      • Kontakt & Sprechstunden
      • Aktuelles und Termine
      • Newsletter, Social Media, Podcast & Videos
      • Stellenausschreibungen
  • Die TU Braunschweig
    • Unser Profil
      • Ziele & Werte
      • Ordnungen und Leitlinien
      • Hochschulentwicklung 2030
      • Ecoversity – die TU Braunschweig als Ökosystem Universität
      • Chancengleichheit
      • Diversity
      • Nachhaltigkeit
      • Fakten & Zahlen
      • Unsere Geschichte
    • Leitung & Organisation
      • Das Präsidium
      • Stabsstellen
      • Verwaltung
      • Einrichtungen
      • Organe, Statusgruppen und Kommissionen
      • Studierendenschaft
    • Karriere
      • Arbeiten an der TU
      • Stellenmarkt
      • Berufsausbildung an der TU
      • Informationen und Angebote für neue Mitarbeitende
    • Fakultäten
      • Carl-Friedrich-Gauß-Fakultät
      • Fakultät für Lebenswissenschaften
      • Fakultät Architektur, Bauingenieurwesen und Umweltwissenschaften
      • Fakultät für Maschinenbau
      • Fakultät für Elektrotechnik, Informationstechnik, Physik
      • Fakultät für Geistes- und Erziehungswissenschaften
      • Institute von A-Z
    • Die TU für alle
      • Gasthörer*innen & Senior*innenstudium
      • Universitätsbibliothek nutzen
      • Das Studierendenhaus
      • Podcasts
    • Veranstaltungen
      • Veranstaltungskalender
      • Angebote für Schüler*innen
      • Hochschulinformationstag (HIT)
  • Suche
  • Schnellzugriff
    IBR Login
    • Bibliothek
    • Mailinglisten
    • Webmail
    • Knowledgebase
    • Wiki
    • Account Management
    • Service-Status
    • Personensuche
    • Webmail
    • cloud.TU Braunschweig
    • Messenger
    • Mensa
    • TUconnect (Studierendenportal)
    • Im Notfall
    • Stud.IP
    • UB Katalog
    • Forschungsinformations-System (FIS)
    • Status GITZ-Dienste
    • Störungsmeldung GB3
    • Informationsportal (Beschäftigte)
    • Linksammlung
    • DE
    • EN
    • Instagram
    • YouTube
    • LinkedIn
    • Mastodon
    • Bluesky

    Menü
    Technische Universität BraunschweigIBR
    • Struktur
    • Fakultäten
    • Carl-Friedrich-Gauß-Fakultät
    • Institute
    • Institut für Betriebssysteme und Rechnerverbund
    • Aktuelle Projekte
    • Computing Optimal Polygons
    Logo IBR
    • Institut für Betriebssysteme und Rechnerverbund
      • News
      • Wir über uns
        • Gesamtes Team
        • Anreise
        • Raumplan
        • Projekte
        • Veröffentlichungen
        • Software
        • News Archiv
      • Connected and Mobile Systems
        • Team
        • Lehrveranstaltungen
        • Abschlussarbeiten
        • Projekte
        • Veröffentlichungen
        • Software
        • Datensätze
      • Verlässliche Systemsoftware
        • Übersicht
        • Team
        • Lehre
        • Arbeiten & Jobs
        • Forschung
        • Publikationen
      • Algorithmik
        • Team
        • Lehrveranstaltungen
        • Abschlussarbeiten
        • Projekte
        • Veröffentlichungen
      • Mikroprozessorlabor
      • Studium
        • Wintersemester 2026/2027
        • Sommersemester 2026
        • Abschlussarbeiten
      • Spin-Offs
        • Docoloc
        • bliq (formerly AIPARK)
        • Confidential Technologies
      • Forschungsverbünde
        • IST.hub

    Computing Optimal Polygons

    Given a set of points S in the plane, it is natural to ask for the polygon that uses all these points as vertices and that is minimal or maximal with respect to covered area or length of the boundary. By distinguishing between simple and general polygons this results in 8 different problems.

    Goals
    Eight different problems in polygon generation.

    The minimum boundary simple polygon is equivalent to the Traveling Salesman Problem (TSP) and therefore NP-hard. Fekete proved that computing a simple polygon with maximum or minimum area is also NP-hard. The same also holds for general polygons with maximum or minimum area. In a recent paper of Fekete et al. NP-hardness was proven for computing non-simple polygons with minimum boundary. However, it is unknown if computing a (simple) polygon with maximum boundary is NP-hard.

    When computing a polygon we work on a complete oriented graph of the point set S where the edges get some weights, e.g. the Euclidean distance between each point for optimizing the boundary of the polygons. In case we want to optimize the area of the polygon, we compute for each edge the area of the triangle that the edge forms with a reference point. If the edge has a Right-To-Left orientation relative to the reference this is the weight of the edge or otherwise we count the area negative. This way, the sum of all used edges is the area of the polygon as depicted in the figure below.

    Area Calculation Area Calculation Area Calculation
    Left: Building triangles. Middle: Triangles with Right-To-Left oriented edges. Right: Triangles with Left-To-Right oriented edges.

    Now, with correct edge weights, we can formulate an Integer Program (IP) seen below. With (1) we ensure that the polygon will have optimized boundary or area. To get a polygon we want to have one incoming and one outgoing edge at each vertex (2). Then we need to take care of non-crossing edges (3)-(4). With these constraints we may get disjoint cycles, hence, we would not have a valid polygon. To avoid those cycles, we add the constraint (5). Because there are up to exponential many cycles, we add the cycle elimination constraints in so called separation steps.

    IP Formulation
    IP Formulation for generating Polygons

    With this IP we can generate polygons with optimized boundary or area. To solve such an IP we use CPLEX in C++. Below you can see an instance which has different solutions for all eight problems.

    Simple minimum area Simple minimum boundary Simple minimum area Simple minimum boundary Simple maximum area Simple maximum boundary Simple maximum area Simple maximum boundary
    Top: Minimizing; Bottom: Maximizing
    From left to right: Area; Boundary; Simple Area; Simple Boundary

    There are still some open problems:

    • Is MaxBound NP-Hard?
    • Is SMaxBound NP-Hard?
    • Is there a more efficient IP to solve the Problems?

    Studentische Arbeiten

    Keine Einträge gefunden.

    Ist hier derzeit keine offene Arbeit zu vergeben? Oder interessiert dich das Projekt, aber es ist einfach nicht das richtige Thema für dich dabei? Dann wende dich einfach direkt an uns! Wir haben laufend Ideen für mögliche Themen in verschiedenen Bereichen, die aber vielleicht im Moment noch nicht zu einer konkreten Aufgabenbeschreibung ausgearbeitet sind. Vielleicht finden wir dann gemeinsam auch für dich eine passende und interessante Aufgabe.

    HiWi Stellen

    Keine Einträge gefunden.

    Projektmitglieder

    NameEMailTelefonRaum
    Andreas Haashaas[[at]]ibr.cs.tu-bs.de
    Dr. Dominik Krupkekrupke[[at]]ibr.cs.tu-bs.de+49 531 3913112317
    Dr. Arne Schmidtaschmidt[[at]]ibr.cs.tu-bs.de+49 531 3913115333

    Veröffentlichungen

    • Sándor P Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph SB Mitchell, Arne Schmidt, Christiane Schmidt and others: Computing nonsimple polygons of minimum perimeter, in International Symposium on Experimental Algorithms, Springer, Seite 134-149, 2016 (fekete2016computing, BibTeX)
    • Melanie Papenberg: Exact Methods for area-optimal Polygons, Master's Thesis, University of Technology Braunschweig, 2014 (Papenberg2014, BibTeX)

    Weitere Informationen

    Bei weiteren Fragen wenden Sie sich bitte an die Projektmitglieder.


    aktualisiert am 16.08.2017, 12:58 (dynamischer Inhalt) von Dr. Arne Schmidt
    http://www.ibr.cs.tu-bs.de/projects/polygon-generation/index.xml · abgerufen am 22.11.2026

    Für alle

    Stellenmarkt der TU Braunschweig
    Jobbörse des Career Service
    Merchandising
    Sponsoring- & Spendenleistungen
    Vertrauenspersonen für Hinweisgeber

    Für Studierende

    Semestertermine
    Lehrveranstaltungen
    Studiengänge von A-Z
    Informationen für Erstsemester
    TUCard

    Interne Tools

    Status GITZ-Dienste
    Handbuch für TYPO3 (Intern)
    Corporate Design-Toolbox (Intern)
    Glossar (DE-EN)
    Meine Daten ändern
    Hochschulöffentliche Bekanntmachungen

    Kontakt

    Technische Universität Braunschweig
    Universitätsplatz 2
    38106 Braunschweig
    Postfach: 38092 Braunschweig
    Telefon: +49 (0) 531 391-0

    Anreise

    © Technische Universität Braunschweig
    Impressum Datenschutz Barrierefreiheit

    Zur anonymisierten Reichweitenmessung nutzt die TU Braunschweig die Software Matomo. Die Daten dienen dazu, das Webangebot zu optimieren.
    Weitere Informationen finden Sie in unserer Datenschutzerklärung.