Publications
Journals
Fixed-Parameter Complexity and Approximability of Norm Maximization
accepted for publication in Discrete & Computational Geometry (DCG)
with
Christian Knauer and Stefan König
Note: sneak
The problem of maximizing the p-th power of a p-norm over a halfspace-presented polytope in R^d is a convex maximization problem which plays a fundamental role in computational convexity.
Approximating Tverberg Points in Linear Time for Any Fixed Dimension
accepted for publication in Discrete & Computational Geometry (DCG)
with
Wolfgang Mulzer
Note: sneak
We show how to find an approximate Tverberg point in d dimensions via a lifting argument, and present several strengthenings of this technique.
A Proof of the Oja-Depth Conjecture in the Plane [
EuroCG version ]
accepted for publication in Computational Geometry - Theory and Applications (CGTA) (Special Issue on the 27th European Workshop on Computational Geometry)
with
Nabil H. Mustafa,
Hans Raj Tiwary
Note: sneak
In this paper, we prove that every planar point-set has an Oja-depth of at most (n^2)/9, which meets the upper bound construction. We also improve the best known bound for the higher-dimensional setting.
Hardness of discrepancy computation and epsilon-net verification in high dimension [
DOI ]
Journal of Complexity (JC), Elsevier 2011
with
Panos Giannopoulos,
Christian Knauer,
Magnus Wahlström
Note: sneak
We show that several versions of discrepancy computation are hard in arbitrary dimension d. Further, we proof a (relative) lower bound of n^d for the problem of deciding whether a given set S is an epsilon-net for another set P (e.g., with respect to half-spaces).
Fixed-parameter tractability and lower bounds for stabbing problems [
DOI ]
Computational Geometry - Theory and Applications (CGTA) (Special Issue on the 25th European Workshop on Computational Geometry), Elsevier 2011.
with
Panos Giannopoulos,
Christian Knauer,
Günter Rote
Note: sneak
This is mainly my Master's Thesis. Among other things, it shows that intersecting disjoint circles with lines in R^2 is W[1]-hard. A well known result by Langerman and Morin shows that covering points is fpt.
Conferences
On the computational complexity of Erdős-Szekeres and related problems in R^3
Accepted at the 21st European Symposium on Algorithms (ESA), Sophia Antipolis, France 2013
with
Panos Giannopoulos,
Christian Knauer
Note: sneak
We show that, given a set of points in R^3, it is NP-hard to determine the largest number of points in convex position. We also show that the problem is W[1]-hard, if certain restrictions are dropped.
Approximating Tverberg Points in Linear Time for Any Fixed Dimension [
arXiv version ]
Accepted at the 28th Symposium on Computational Geometry (SoCG), Chapel Hill, NC, USA 2012
with
Wolfgang Mulzer
Note: sneak
We present a simple algorithm that computes an approximate Tverberg point in R^d in linear time, and several improvements. An extended version of this paper has appeared in DCG (see above).
On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems [
DROPS |
pdf |
talk ]
28th Symposium on Theoretical Aspects of Computer Science (STACS), Dortmund 2011
with
Christian Knauer,
Hans Raj Tiwary
Note: sneak
This paper contains proofs that the following are NP-(and W[1]-)hard problems:
Thm 1: Given d point sets in R^d, is there a Ham-Sandwich cut through the origin?
Thm 2: Given n points in R^d, is the origin in the convex hull of d points?
Observe that the latter can easily be solved in polynomial time if we ask for d+1 points. (LP + Caratheodory)
In Preparation
A Lower Bound for Shallow Partitions
[
arXiv ]
in preparation
with
Wolfgang Mulzer
Note: sneak
We give a lower bound of Omega(log(n/k)/ log log(n/k))
for the crossing number of shallow partitions in the plane.
Weakly Reviewed Conferences
A Lower Bound for Shallow Partitions
[
pdf ]
In Proceedings of the 28th European Workshop on Computational Geometry (EuroCG), Assisi, March 2012.
with
Wolfgang Mulzer
Note: sneak
We give a lower bound of Omega(log(n/k)/ log log(n/k))
for the crossing number of shallow partitions in the plane.
Approximating Tverberg Points in Linear Time for Any Fixed Dimension
[
pdf ]
In Proceedings of the 28th European Workshop on Computational Geometry (EuroCG), Assisi, March 2012.
with
Wolfgang Mulzer
Note: sneak
We show how to find an approximate Tverberg point in d dimensions via a lifting argument, and present several strengthenings of this technique.
Erdős-Szekeres is NP-hard in 3 dimensions - and what now?
[
pdf ]
In Proceedings of the 28th European Workshop on Computational Geometry (EuroCG), Assisi, March 2012.
with
Christian Knauer
Note: sneak
We show that finding the largest set in convex position is NP-hard in 3 dimensions, in contrast to the (long known) planar case, for which it is in P.
A Proof of the Oja-Depth Conjecture in the Plane
[
pdf |
talk ]
In Proceedings of the 27th European Workshop on Computational Geometry (EuroCG), Morschach, Switzerland, March 2011.
with
Nabil H. Mustafa,
Hans Raj Tiwary
Note: sneak
Extended version to be submitted. See above.
Hardness of discrepancy and related problems parameterized by the dimension [
pdf |
talk ]
In Proceedings of the 26th European Workshop on Computational Geometry (EuroCG), pp. 173-176, Dortmund, March 2010.
with
Panos Giannopoulos,
Christian Knauer,
Magnus Wahlström
Note: sneak
This paper shows that computing the discrepancy of a higher dimensional point-set is W[1]-(and NP-)hard. An extended version is to be submitted.
Fixed-parameter tractability and lower bounds for stabbing problems [
pdf ]
In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), pp. 281-284, Brussels, Belgium, March 2009.
with
Panos Giannopoulos,
Christian Knauer,
Günter Rote
Note: sneak
Extended version appeared in CGTA, see above.
Other
Polynomial Bounds on the Slicing Number [
pdf ]
http://arxiv.org/abs/1004.3381, World Wide Web, July 2010 (withdrawn)
with
Matthias Lenz
Note: sneak
Unfortunately, most of the results mentioned here were already known under the name of "d-separated interval piercing".
Still, because of the work we put into this, we leave the paper available to the public here, also because one might find the references useful.
See
Gabor Tardos' Homepage for an excellent survey.