Obtaining lower bounds using artificial components

DOI10.1016/0020-0190(87)90141-4zbMath0653.68023OpenAlexW1995309500MaRDI QIDQ1107991

Prakash V. Ramanan

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90141-4

zbMATH Keywords

connected componentslower boundscomputational geometryproblem transformationalgebraic decision tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (8)

SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS ⋮ PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS ⋮ Processing an Offline Insertion-Query Sequence with Applications ⋮ An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains ⋮ Computing the minimum Hausdorff distance between two point sets on a line under translation ⋮ PAC-learning in the presence of one-sided classification~noise ⋮ Lower bounds for maximal and convex layers problems ⋮ Decision trees: Old and new results.

Cites Work

• Unnamed Item
• Geometric complexity of some location problems
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees

This page was built for publication: Obtaining lower bounds using artificial components