9 citations · 20 across the 5 of their papers we have counts for
8 papers
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
François Dross, Krzysztof Fleszar, Karol Węgrzycki +1
In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that con…
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity
Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar +2
We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizon…
A PTAS for Euclidean TSP with Hyperplane Neighborhoods
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma +1
In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that vi…
The Complexity of Drawing Graphs on Few Lines and Few Planes
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp +3
It is well known that any graph admits a crossing-free straight-line drawing in and that any planar graph admits the same even in . For a graph and…
Minimum Rectilinear Polygons for Given Angle Sequences
William S. Evans, Krzysztof Fleszar, Philipp Kindermann +3
A rectilinear polygon is a polygon whose edges are axis-aligned. Walking counterclockwise on the boundary of such a polygon yields a sequence of left turns and right turns. The num…
New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase
We study the classical NP-hard problems of finding maximum-size subsets from given sets of terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint p…
Colored Non-Crossing Euclidean Steiner Forest
Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann +3
Given a set of -colored points in the plane, we consider the problem of finding trees such that each tree connects all points of one color class, no two trees cross, and the…
Polylogarithmic Approximation for Generalized Minimum Manhattan Networks
Aparna Das, Krzysztof Fleszar, Stephen Kobourov +3
Given a set of terminals, which are points in -dimensional Euclidean space, the minimum Manhattan network problem (MMN) asks for a minimum-length rectilinear network that co…