Finding points in general position

DOI10.1142/S021819591750008XMaRDI QIDQ4605338zbMATH OpenOpenAlexWikidataFDO

Authors Vincent Froese, André Nichterlein, Rolf Niedermeier, Iyad 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 complexityparameterized complexityhardness of approximationkernelizationpoint line cover

Mathematics Subject Classification ID

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

Abstract: We study computational aspects of the General Position Subset Selection problem defined as follows: Given a set of points in the plane, find a maximum-cardinality subset of points in general position. We prove that General Position Subset Selection is NP-hard, APX-hard, and give several fixed-parameter tractability results as well as a subexponential running time lower bound based on the Exponential Time Hypothesis.

Recommendations

• On the General Position Subset Selection Problem
• On the computational complexity of Erdős-Szekeres and related problems in \(\mathbb{R}^{3}\)
• An improved lower bound for general position subset selection
• Kernelization of the subset general position problem in geometry
• Sets in almost general position

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• Advice classes of parametrized tractability
• 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
• Covering things with things
• Fundamentals of parameterized complexity
• Maximal Independent Subsets in Steiner Systems and in Planar Sets
• On a Problem of Heilbronn
• On some metric and combinatorial geometric problems
• On the General Position Subset Selection Problem
• On the complexity of k-SAT
• Point line cover: the easy kernel is essentially tight
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Some APX-completeness results for cubic graphs
• Some advances in the no-three-in-line problem
• Subquadratic algorithms for algebraic generalizations of 3SUM
• The Group of Rational Points on the Unit Circle
• The No-Three-In-Line Problem
• The design of approximation algorithms
• The exact fitting problem in higher dimensions
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Which problems have strongly exponential complexity?

Cited in

(26)

• The iteration time and the general position number in graph convexities
• The edge general position number of some graphs
• Mutual-visibility and general position in double graphs and in Mycielskians
• The parameterized complexity of finding point sets with hereditary properties
• Characterization of classes of graphs with large general position number
• On the general position problem on Kneser graphs
• On the General Position Number of Complementary Prisms
• Computational complexity aspects of point visibility graphs
• On the vertex position number of graphs
• The general position avoidance game and hardness of general position games
• Problem of identifying a point
• On the complexity of finding and counting solution-free sets of integers
• The general position achievement game played on graphs
• A general position problem in graph theory
• The general position problem on Kneser graphs and on some graph operations
• Computational complexity of the -Ham-Sandwich problem
• Kernelization of the subset general position problem in geometry
• Characterization of general position sets and its applications to cographs and bipartite graphs
• A note on the edge general position number of cactus graphs
• Clique-width of point configurations
• On independent position sets in graphs
• General position subset selection in line arrangements
• An improved lower bound for general position subset selection
• On the general position number of two classes of graphs
• The edge general position problem
• On the general position number of Mycielskian graphs

This page was built for publication: Finding points in general position

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4605338)