Publications
Journals
- On the computational complexity of Erdős-Szekeres and related problems in R3 (with C. Knauer and D. Werner)
Accepted at J. of Computational Geometry
- Minimum cell connection in line segment arrangements. (with H. Alt, S. Cabello, and C. Knauer)
International J. of Computational Geometry and Applications, 27(3), pp. 159--176, WSPC, 2017
-
The complexity of separating points in the plane. (with S. Cabello)
Algorithmica, 74(2), pp. 643-663, Springer, 2016
-
Fixed-parameter tractability and lower bounds for stabbing
problems. (with C. Knauer, G. Rote, and D. Werner)
Computational Geometry Theory and Applications 46(7), pp. 839--860, Elsevier, 2013
-
Hardness of discrepancy and related problems parameterized by
the dimension. (with C. Knauer, M. Wahlstrom, and D. Werner)
J. Complexity (28), pp. 162--176, Elsevier, 2012
-
Geometric clustering: fixed-parameter tractability and lower
bounds with respect to the dimension. (with with S. Cabello,
C. Knauer, D. Marx, and G. Rote)
ACM Transactions on Algorithms, 7 (4), pp. 43:1--43:27, ACM, 2011
-
Computing geometric minimum dilation graphs is NP-hard. (with R. Klein, C. Knauer, M. Kutz, and D. Marx)
International J. Computational Geometry and Applications, 20 (2), pp. 147--173, WSPC, 2010
-
Maximizing the Area of Overlap of two Unions of Disks under
Rigid Motion. (with M. de Berg, S. Cabello, C. Knauer, R. van Oostrum, and R.C. Veltkamp)
International J. Computational Geometry and Applications, 19 (6), pp. 533--556, WSPC, 2009
-
Improving the stretch factor of a geometric network by edge
augmentation. (with M. Farshi and J. Gudmundsson)
SIAM J. on Computing, 38 (1), pp. 226--240, SIAM, 2008
-
Matching Point Sets with respect to the Earth Mover's
Distance. (with S. Cabello, C. Knauer, and G. Rote)
Computational Geometry Theory and Applications, 39, pp. 118--133,
Elsevier, 2008
-
On the parameterized complexity of d-dimensional point set
pattern matching. (with S. Cabello and C. Knauer)
Information Processing Letters, 105, pp. 73--77, Elsevier, 2008
-
Parameterized complexity of geometric problems. (with C. Knauer and
S. Whitesides)
The Computer Journal, 51, pp. 372--385, Oxford University Press, 2008
Conferences, Workshops, arXiv
- QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
(with É. Bonnet and E.J. Kim and P. Rzążewski and F. Sikora)
arXiv:1710.00386. Accepted at SoCG 2018.
- Orthogonal Terrain Guarding is NP-complete
(with É. Bonnet)
arXiv:1710.00386. Accepted at SoCG 2018.
- On the parameterized complexity of red-blue points separation
(with É. Bonnet and M. Lampis)
IPEC 2017.
- Low-Crossing Spanning Trees: an Alternative Proof and Experiments
(with M. Konzack and W. Mulzer)
EuroCG 2014.
- On the computational complexity of Erdős-Szekeres and related problems in R3
(with C. Knauer and D. Werner)
ESA 2013.
- Finding a largest empty convex subset in space is W[1]-hard
(with C. Knauer)
Abstracts of 29th EuroCG, 2013.
- The complexity of separating points in the plane
(with S. Cabello)
SoCG 2013. (Preliminary version in abstracts of EuroCG 2013.)
- Minimum cell connection in line segment arrangements
(with H. Alt, S. Cabello, and C. Knauer)
Abstracts of 27th EuroCG, 2011.
(Presented as: 'On some connection problems in straight-line segment arrangements'.)
- Milling a graph with turn costs: A parameterized complexity perspective
(with M. Fellows, C. Knauer, C. Paul, F. Rosamond, S. Whitesides, and N. Yu)
WG 2010, LNCS 6410.
- Hardness of discrepancy and related problems parameterized by the dimension
(with C. Knauer, M. Wahlstrom, and D. Werner)
Abstracts of 26th EuroCG, 2010.
- The parameterized complexity of some geometric problems in unbounded dimension
(with C. Knauer and G. Rote)
IWPEC 2009, LNCS 5917.
- Fixed-parameter tractability and lower bounds for stabbing problems
(with C. Knauer, G. Rote, and D. Werner)
Abstracts of 25th EuroCG, 2009.
- Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension
(with S. Cabello, C. Knauer, and G. Rote)
SODA08, 2008.
- Minimum-dilation tour (and path) is NP-hard.
(with C. Knauer and D. Marx)
Abstracts of 23rd EuroCG, 2007.
- On the parameterized complexity of d-dimensional point set pattern matching.
(With S. Cabello and C. Knauer)
IWPEC'06, LNCS 4169, 2006.
- Matching Point Sets with respect to the Earth Mover's Distance.
(With S. Cabello, C. Knauer, and G. Rote.)
ESA'05, LNCS 3669, and EWCG'05.
- Finding the best shortcut in a geometric network.
(With M. Farshi and J. Gudmundsson)
SoCG, 2005. A short version appeared at EWCG'05.
- Maximizing the area of overlap of two unions of disks under rigid motion.
(With M. de Berg, S. Cabello, C. Knauer, R. van Oostrum, and R.C. Veltkamp.)
Proc. 9th Scandinavian Workshop on Algorithm Theory, LNCS 3111,
2004. Also in EWCG'04.
- Using transportation distances for measuring melodic similarity.
(With R. Typke, R. C. Veltkamp, F. Wiering, and R. van Oostrum.)
Proc. 4th International Conference on Music Information Retrieval, Baltimore, 2003.
- A Pseudo-Metric for Weighted Point Sets.
(With R.C. Veltkamp.)
Proc. 7th ECCV(3), LNCS 2352, 2002.
Other
- Geometric matching of weighted point sets PhD Thesis, Utrecht University, 2005.
- The Area of Overlap of two Unions of Convex Objects under Translation.
(With C. Knauer, M. de Berg, R. van Oostrum, and R.C. Veltkamp.)
Utrecht University, Technical Report UU-CS-2003-025, 2003.