Opendata, web and dolomites


Complexity Inside NP - A Computational Geometry Perspective

Total Cost €


EC-Contrib. €






Project "CGinsideNP" data sheet

The following table provides information about the project.


Organization address
city: BERLIN
postcode: 14195

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Germany [DE]
 Total cost 1˙486˙800 €
 EC max contribution 1˙486˙800 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2017-STG
 Funding Scheme ERC-STG
 Starting year 2018
 Duration (year-month-day) from 2018-02-01   to  2023-01-31


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    FREIE UNIVERSITAET BERLIN DE (BERLIN) coordinator 1˙486˙800.00


 Project objective

Traditional complexity theory focuses on the dichotomy between P and NP-hard problems. Lately, it has become increasingly clear that this misses a major part of the picture. Results by the PI and others offer glimpses on a fascinating structure hiding inside NP: new computational problems that seem to lie between polynomial and NP-hard have been identified; new conditional lower bounds for problems with large polynomial running times have been found; long-held beliefs on the difficulty of problems in P have been overturned. Computational geometry plays a major role in these developments, providing some of the main questions and concepts.

We propose to explore this fascinating landscape inside NP from the perspective of computational geometry, guided by three complementary questions:

(A) What can we say about the complexity of search problems derived from existence theorems in discrete geometry? These problems offer a new perspective on complexity classes previously studied in algorithmic game theory (PPAD, PLS, CLS). Preliminary work indicates that they have the potential to answer long-standing open questions on these classes.

(B) Can we provide meaningful conditional lower bounds on geometric problems for which we have only algorithms with large polynomial running time? Prompted by a question raised by the PI and collaborators, such lower bounds were developed for the Frechet distance. Are similar results possible for problems not related to distance measures? If so, this could dramatically extend the traditional theory based on 3SUM-hardness to a much more diverse and nuanced picture.

(C) Can we find subquadratic decision trees and faster algorithms for 3SUM-hard problems? After recent results by Pettie and Gronlund on 3SUM and by the PI and collaborators on the Frechet distance, we have the potential to gain new insights on this large class of well-studied problems and to improve long-standing complexity bounds for them.


year authors and title journal last update
List of publications.
2019 Cheng, Siu-Wing; Chiu, Man-Kwun
Implicit Manifold Reconstruction
published pages: , ISSN: , DOI:
2 2019-11-22
2019 Aichholzer, Oswin; Balko, Martin; Hoffmann, Michael; Kynčl, Jan; Mulzer, Wolfgang; Parada, Irene; Pilz, Alexander; Scheucher, Manfred; Valtr, Pavel; Vogtenhuber, Birgit; Welzl, Emo
Minimal Representations of Order Types by Geometric Graphs
published pages: , ISSN: , DOI:
GD 2019 2 2019-11-22
2019 Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir
Triangles and Girth in Disk Graphs and Transmission Graphs
published pages: 64:1-64:14, ISSN: , DOI: 10.4230/lipics.esa.2019.64
ESA 2019 2019-11-22
2019 Chen, Ke; Dumitrescu, Adrian; Mulzer, Wolfgang; Tóth, Csaba D.
On the Stretch Factor of Polygonal Chains
published pages: 56:1–56:14, ISSN: , DOI: 10.4230/lipics.mfcs.2019.56
MFSC 2019 3 2019-11-22
2019 Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer
Maximum Matchings in Geometric Intersection Graphs
published pages: , ISSN: , DOI:
2018 Mulzer, Wolfgang
Five Proofs of Chernoff\'s Bound with Applications
published pages: , ISSN: 0252-9742, DOI:
Bulletin of the EATCS 3 2019-10-03
2018 Bahareh Banyassady, Matias Korman, Wolfgang Mulzer
Computational Geometry Column 67
published pages: 77-94, ISSN: 0163-5700, DOI: 10.1145/3232679.3232692
ACM SIGACT News 49/2 2019-10-03
2018 Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth
Routing in Unit Disk Graphs
published pages: 830-848, ISSN: 0178-4617, DOI: 10.1007/s00453-017-0308-2
Algorithmica 80/3 2019-10-03
2019 Aruni Choudhary, Wolfgang Mulzer
No-dimensional Tverberg Theorems and Algorithms
published pages: , ISSN: , DOI:
2018 Wolfgang Mulzer, Yannik Stein
Computational Aspects of the Colorful Carathéodory Theorem
published pages: 720-755, ISSN: 0179-5376, DOI: 10.1007/s00454-018-9979-y
Discrete & Computational Geometry 60/3 2019-10-03
2018 Agarwal, Pankaj K.; Kaplan, Haim; Kipper, Geva; Mulzer, Wolfgang; Rote, Günter; Sharir, Micha; Xiao, Allen
Approximate Minimum-Weight Matching with Outliers under Translation
published pages: , ISSN: , DOI: 10.4230/lipics.isaac.2018.26
ISAAC 2018 1 2019-10-03
2018 Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein
Time–space trade-offs for triangulations and Voronoi diagrams
published pages: 35-45, ISSN: 0925-7721, DOI: 10.1016/j.comgeo.2017.01.001
Computational Geometry 73 2019-10-03
2019 Agarwal, Pankaj K.; Cohen, Ravid; Halperin, Dan; Mulzer, Wolfgang
Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead
published pages: , ISSN: , DOI: 10.4230/lipics.socg.2019.26
SoCG 2019 3 2019-10-03
2018 Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein
Improved time-space trade-offs for computing Voronoi diagrams
published pages: 191-212, ISSN: 1920-180X, DOI: 10.20382/jocg.v9i1a6
JoCG 9(1) 2019-10-03
2019 Hee-Kap Ahn, Sang Won Bae, Jongmin Choi, Matias Korman, Wolfgang Mulzer, Eunjin Oh, Ji-won Park, André van Renssen, Antoine Vigneron
Faster algorithms for growing prioritized disks and rectangles
published pages: 23-39, ISSN: 0925-7721, DOI: 10.1016/j.comgeo.2019.02.001
Computational Geometry 80 2019-10-03
2019 Barba, Luis; Mulzer, Wolfgang
Asymmetric Convex Intersection Testing
published pages: , ISSN: , DOI: 10.4230/oasics.sosa.2019.9
SOSA 2019 1 2019-10-03
2018 Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth
Spanners for Directed Transmission Graphs
published pages: 1585-1609, ISSN: 0097-5397, DOI: 10.1137/16m1059692
SIAM Journal on Computing 47/4 2019-10-03
2018 Matias Korman, Stefan Langerman, Wolfgang Mulzer, Alexander Pilz, Maria Saumell, Birgit Vogtenhuber
The dual diameter of triangulations
published pages: 243-252, ISSN: 0925-7721, DOI: 10.1016/j.comgeo.2017.06.008
Computational Geometry 68 2019-10-03
2019 Agarwal, Pankaj K.; Cohen, Ravid; Halperin, Dan; Mulzer, Wolfgang
Dynamic Maintenance of the Lower Envelope of Pseudo-Lines
published pages: , ISSN: , DOI:
1 2019-10-03
2019 Wolfgang Mulzer, Natalia Shenkman
A Constructive Proof of a Concentration Bound for Real-Valued Random Variables
published pages: , ISSN: , DOI:
2019 Chiu, Man-Kwun; Cleve, Jonas; Klost, Katharina; Korman, Matias; Mulzer, Wolfgang; van Renssen, André; Roeloffzen, Marcel; Willert, Max
Routing in Histograms
published pages: , ISSN: , DOI:
1 2019-10-03
2018 Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, Max Willert:
Stabbing pairwise intersecting disks by five points
published pages: , ISSN: , DOI: 10.4230/lipics.isaac.2018.50
ISAAC 2019 2019-10-03

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "CGINSIDENP" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "CGINSIDENP" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

EVOMENS (2020)

The evolution of menstruation in primates

Read More  

InsideChromatin (2019)

Towards Realistic Modelling of Nucleosome Organization Inside Functional Chromatin Domains

Read More  


The Mass Politics of Disintegration

Read More