Technische Universität Braunschweig
  • Study & Teaching
    • Beginning your Studies
      • Prospective Students
      • Degree Programmes
      • Application
      • Why TU Braunschweig?
    • During your Studies
      • Fresher's Hub
      • Term Dates
      • Courses and Qualifications
      • Practical information
      • Beratungsnavi
      • Financing and Costs
      • Special Circumstances
      • Health & Wellbeing
      • Campus life
    • At the End of your Studies
      • Career Service
      • Alumni
      • Discontinuation and Pre-Certification
      • After graduation
    • Strategies and Quality Management
      • TU Teaching Award
    • For Teaching Staff
      • Strategy, Offers and Information
      • Learning Management System Stud.IP
    • Contact
      • Study Service Centre
      • Academic Advice Service
      • Student Office
      • Department 16 - Academic and Student Affairs
      • Career Service
  • Research
    • Research Profile
      • Core Research Areas
      • Clusters of Excellence at TU Braunschweig
      • Research Projects
      • Research Centres
      • Professors‘ Research Profiles
    • Early Career Researchers
      • Support in the early stages of an academic career
      • PhD-Students
      • Postdocs
      • Junior research group leaders
      • Junior Professorship and Tenure-Track
      • Habilitation
      • Service Offers for Scientists
    • Research Data & Transparency
      • Transparency in Research
      • Research Data
      • Open Access Strategy
    • Research Funding
      • Research Funding Network
      • Research funding
    • Contact
      • Research Services
      • Academy for Graduates
  • Transfer
    • Transfer profile
      • Transfer strategy "TIES® with Impact"
      • Technology Transfer
      • Knowledge Transfer
      • Relationship Management
    • Innovation
      • Startups
      • Patents
    • Offers for schools and pupils
    • For enterprises
      • Friends & Supporters
    • For Alumni*ae
    • For everyone
  • International
    • International Students
      • Why Braunschweig?
      • Degree seeking students
      • Exchange Studies
      • TU Braunschweig Summer School
      • Students from German Schools Abroad
      • Refugees
      • International Student Support
      • International Career Service
    • Going Abroad
      • Studying abroad
      • Internships abroad
      • Teaching and research abroad
      • Working abroad
    • International Researchers
      • Welcome Support for International Researchers
      • Service for Host Institutes
    • Language and intercultural competence training
      • Learning German
      • Learning Foreign Languages
      • Intercultural Communication
    • International Profile
      • Internationalisation
      • International Cooperations
      • Strategic partnerships
      • International networks
    • International House
      • About us
      • Contact & Office Hours
      • News and Events
      • Newsletter, Podcast & Videos
      • Job Advertisements
  • TU Braunschweig
    • Our Profile
      • Aims & Values
      • Regulations and Guidelines
      • The University Development Initiative 2030
      • Ecoversity – the TU Braunschweig as a university ecosystem
      • Equal Opportunity
      • Diversity
      • Sustainability
      • Facts & Figures
      • Our History
    • Presidency & Organisation
      • Executive Board
      • Designated Offices
      • Administration
      • Facilities
      • Committees
      • Student body
    • Career
      • Working at TU Braunschweig
      • Vacancies
      • Information and Offers for New Employees
    • Faculties
      • Carl-Friedrich-Gauß-Fakultät
      • Faculty of Life Sciences
      • Faculty of Architecture, Civil Engineering and Environmental Sciences
      • Faculty of Mechanical Engineering
      • Faculty of Electrical Engineering, Information Technology, Physics
      • Faculty of Humanities and Education
      • Institutes from A to Z
    • Events
  • Search
  • Quicklinks
    IBR Login
    • Library
    • Mailinglists
    • Webmail
    • Knowledge Base
    • Wiki
    • Account Management
    • Services Status
    • People Search
    • Webmail
    • cloud.TU Braunschweig
    • Messenger
    • Cafeteria
    • TUconnect (student platform)
    • Emergency
    • Stud.IP
    • Library Catalogue
    • Research Information System
    • Information Portal (employees)
    • Link Collection
    • DE
    • EN
    • Instagram
    • YouTube
    • LinkedIn
    • Mastodon
    • Bluesky

    Menu
    Technische Universität BraunschweigIBR
    • Organisation
    • Faculties
    • Carl-Friedrich-Gauß-Fakultät
    • Institutes
    • Institute of Operating Systems and Computer Networks
    • Current Projects
    • Computing Optimal Polygons
    Logo IBR
    • Institute of Operating Systems and Computer Networks
      • News
      • About us
        • Whole Team
        • Directions
        • Floor Plan
        • Projects
        • Publications
        • Software
        • News Archive
      • Connected and Mobile Systems
        • Team
        • Courses
        • Theses & Jobs
        • Projects
        • Publications
        • Software
        • Datasets
      • Reliable System Software
        • Overview
        • Team
        • Teaching
        • Theses & Jobs
        • Research
        • Publications
      • Algorithms
        • Team
        • Courses
        • Theses
        • Projects
        • Publications
      • Microprocessor Lab
      • Education
        • Winter 2026/2027
        • Summer 2026
        • Theses
      • Spin-Offs
        • Docoloc
        • bliq (formerly AIPARK)
        • Confidential Technologies
      • Research Cooperations
        • 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?

    Theses

    No entries found.

    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 Jobs

    No entries found.

    Project members

    NameEMailPhoneRoom
    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

    Publications

    • 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, pages 134-149, 2016 (fekete2016computing, BibTeX)
    • Melanie Papenberg: Exact Methods for area-optimal Polygons, Masterarbeit, University of Technology Braunschweig, 2014 (Papenberg2014, BibTeX)

    Further Information

    You are welcome to contact the project members for further information.


    last changed 2017-08-16, 12:58 (dynamic content) by Dr. Arne Schmidt
    http://www.ibr.cs.tu-bs.de/projects/polygon-generation/index.xml · retrieved 2026-11-22

    For All Visitors

    Vacancies of TU Braunschweig
    Career Service' Job Exchange 
    Merchandising

    For Students

    Term Dates
    Courses
    Degree Programmes
    Information for Freshman
    TUCard

    Internal Tools

    Glossary (GER-EN)
    Change your Personal Data

    Contact

    Technische Universität Braunschweig
    Universitätsplatz 2
    38106 Braunschweig

    P. O. Box: 38092 Braunschweig
    GERMANY

    Phone: +49 (0) 531 391-0

    Getting here

    © Technische Universität Braunschweig
    Legal Notice Privacy Accessibility

    TU Braunschweig uses the software Matomo for anonymised web analysis. The data serve to optimise the web offer.
    You can find more information in our data protection declaration.