Minimum Cell Connection in Line Segment Arrangements

DOI10.1142/S0218195917500017zbMath1423.68532MaRDI QIDQ3132917

Christian Knauer, Panos Giannopoulos, Sergio Cabello, Helmut Alt

Publication date: 31 January 2018

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

path homotopysegment arrangementcell connection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Related Items

Minimum cuts in geometric intersection graphs ⋮ Hardness of minimum barrier shrinkage and minimum installation path ⋮ Extremal problems on ray sensor configurations ⋮ How to Navigate Through Obstacles ⋮ Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle ⋮ The complexity of separating points in the plane

Cites Work

• Unnamed Item
• Unnamed Item
• Improved algorithms for feedback vertex set problems
• On grid intersection graphs
• On the general motion-planning problem with two degrees of freedom
• Ray shooting in polygons using geodesic triangulations
• Testing homotopy for paths in the plane
• On the complexity of barrier resilience for fat regions
• The parameterized complexity of some minimum label problems
• Approximation algorithms and hardness results for labeled connectivity problems
• The Number of Shortest Paths on the Surface of a Polyhedron
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• A POLYNOMIAL-TIME ALGORITHM FOR COMPUTING THE RESILIENCE OF ARRANGEMENTS OF RAY SENSORS
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• On lazy randomized incremental construction

This page was built for publication: Minimum Cell Connection in Line Segment Arrangements