Optimal Convex Decompositions

Machine intelligence and pattern recognitionPublished 1 January 1985

Citations131

TL;DR

The problem of decomposing a non-convex simple polygon into a minimum number of convex polygons is solved and the decomposition allows for the introduction of Steiner points.

Abstract

The problem of decomposing a non-convex simple polygon into a minimum number of convex polygons is solved. The decomposition allows for the introduction of Steiner points. Two algorithms are proposed. The first verifies that the problem is doable in polynomial time. The second provides an efficient method. Along the way, numerous results of independent interest in pure geometry as well as geometric complexity are stated.

Keywords

Computer ScienceEngineering

The Design and Analysis of Computer Algorithms

9,456 Citations1974Alfred V. Aho, John E. Hopcroft

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.

Information Processing LettersTriangulating a simple polygon

299 Citations1978M. R. Garey, David S. Johnson +2 more

Journal of AlgorithmsA linear algorithm for computing the visibility polygon from a point

242 Citations1981Hossam El Gindy, David Avis

A linear, and thus optimal, algorithm is exhibited for solving the hidden-line problem in two dimensions, a recurrent problem in computer graphics.

SIAM Journal on ComputingConvex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm

240 Citations1984Bernard Chazelle

A quadratic lower bound on the complexity of the polyhedron partitioning problem is established, and an algorithm is described that produces a number of convex parts within a constant factor of optimal in the worst case.

IEEE Transactions on Information TheorySome NP-hard polygon decomposition problems

201 Citations1983Joseph O’Rourke, Kenneth J. Supowit

Three polygon decomposition problems are shown to be NP-hard and thus unlikely to admit efficient algorithms, and the polygonal region is permitted to contain holes.

IEEE Transactions on ComputersDecomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition

136 Citations1975Huihui Feng, T. Pavlidis

A technique for decomposition of polygons into simpler components is described and illustrated with applications in the analysis of handwritten Chinese characters and chromosomes.

Lecture notes in computer scienceThe power of non-rectilinear holes

126 Citations1982Andrzej Lingas

Decomposing a polygon into its convex parts

112 Citations1979Bernard Chazelle, David Dobkin

This work considers the problem of decomposing a simple (non-convex) polygon into the union of a minimal number of convex polygons and reaches polynomial time bounded algorithms for exact solution as well as low degree polynometric time bounded algorithm/or approximation methods.

IEEE Transactions on ComputersDecomposition of Polygons into Convex Sets

81 Citations1978Schachter

A method is presented for decomposing polygons into convex sets based upon a Delaunay tessellation of the polygon and implemented as a divide-and-conquer technique.

Computational geometry and convexity

79 Citations1980Bernard Chazelle

To assert the power of convexity as a crucial factor of efficiency in computational geometry and to show how non-convex design can also benefit from this feature, a class of practical algorithms for detecting intersections of lines, planes, polygons, and polyhedra in two and three dimensions is presented.