Finding Points in General Position

DOI10.1142/S021819591750008XzbMath1386.68196arXiv1508.01097OpenAlexW2963585508WikidataQ130209199 ScholiaQ130209199MaRDI QIDQ4605338

André Nichterlein, Rolf Niedermeier, Vincent Froese, Iyad A. Kanj

Publication date: 22 February 2018

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

Full work available at URL: https://arxiv.org/abs/1508.01097

zbMATH Keywords

computational complexityhardness of approximationparameterized complexitykernelizationpoint line cover

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)

Related Items (14)

The general position achievement game played on graphs ⋮ The general position avoidance game and hardness of general position games ⋮ Computational complexity aspects of point visibility graphs ⋮ On the complexity of finding and counting solution-free sets of integers ⋮ A GENERAL POSITION PROBLEM IN GRAPH THEORY ⋮ Characterization of general position sets and its applications to cographs and bipartite graphs ⋮ Characterization of classes of graphs with large general position number ⋮ The general position problem on Kneser graphs and on some graph operations ⋮ Clique-width of point configurations ⋮ On the general position problem on Kneser graphs ⋮ On the General Position Number of Complementary Prisms ⋮ On the general position number of two classes of graphs ⋮ The edge general position problem ⋮ On independent position sets in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Advice classes of parametrized tractability
• On some metric and combinatorial geometric problems
• Some advances in the no-three-in-line problem
• Some APX-completeness results for cubic graphs
• Which problems have strongly exponential complexity?
• The exact fitting problem in higher dimensions
• Some results on point visibility graphs
• Covering things with things
• The Design of Approximation Algorithms
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Maximal Independent Subsets in Steiner Systems and in Planar Sets
• The Group of Rational Points on the Unit Circle
• Point Line Cover
• On the General Position Subset Selection Problem
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• The No-Three-In-Line Problem
• On a Problem of Heilbronn
• On the complexity of \(k\)-SAT

This page was built for publication: Finding Points in General Position