What question did this study set out to answer?

This research aims to explore the complexity of fundamental problems in computational geometry and present new fast algorithms.

January 1, 1975

Geometric complexity

Key Points

This research aims to explore the complexity of fundamental problems in computational geometry and present new fast algorithms.
Examined the complexity of various problems within computational geometry.
Introduced and analyzed several fast algorithms.
Derived upper and lower bounds for problems related to sets of points, lines, and polygons.
Identified key upper and lower bounds for geometric problems.
Presented algorithms that improve computational efficiency in geometric analysis.
Established links between classical theorems and modern algorithmic approaches.

Abstract

The complexity of a number of fundamental problems in computational geometry is examined and a number of new fast algorithms are presented and analyzed. General methods for obtaining results in geometric complexity are given and upper and lower bounds are obtained for problems involving sets of points, lines, and polygons in the plane. An effort is made to recast classical theorems into a useful computational form and analogies are developed between constructibility questions in Euclidean geometry and computability questions in modern computational complexity.

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Discussion

Authors

Michael Ian Shamos

Carnegie Mellon University

Actions

References and Citations

Connected Papers

Building similarity graph...

Analyzing shared references across papers

Geometric complexity

Key Points

Abstract

Citation Network

Connected Papers

Discussion

Authors

Actions

References and Citations

Citation Network

Connected Papers

Discussion

Cite this study

Also consider

Also consider