Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron

Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. Fukuda, K., Liebling, T. M., & Margot, F. Computational Geometry, 8(1):1--12, June, 1997.

Paper doi abstract bibtex

In this paper, we investigate the applicability of backtrack technique to solve the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtrack algorithm for the face enumeration problem whose space complexity is polynomial in the input size, but the vertex enumeration problem requires a backtrack algorithm to solve a decision problem, called the restricted vertex problem, for each output, which is shown to be NP-complete. Some related NP-complete problems associated with a system of linear inequalities are also discussed, including the optimal vertex problems for polyhedra and arrangements of hyperplanes.

@article{ Fukuda1997,
  abstract = {In this paper, we investigate the applicability of backtrack technique to solve the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtrack algorithm for the face enumeration problem whose space complexity is polynomial in the input size, but the vertex enumeration problem requires a backtrack algorithm to solve a decision problem, called the restricted vertex problem, for each output, which is shown to be NP-complete. Some related NP-complete problems associated with a system of linear inequalities are also discussed, including the optimal vertex problems for polyhedra and arrangements of hyperplanes.},
  author = {Fukuda, Komei and Liebling, Thomas M. and Margot, Fraņ{c}ois},
  doi = {10.1016/0925-7721(95)00049-6},
  file = {:Users/KunihiroWASA/Dropbox/paper/1997/Fukuda, Liebling, Margot, Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, 1997.pdf:pdf},
  issn = {09257721},
  journal = {Computational Geometry},
  month = {June},
  number = {1},
  pages = {1--12},
  title = {{Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron}},
  url = {http://www.sciencedirect.com/science/article/pii/0925772195000496 http://linkinghub.elsevier.com/retrieve/pii/0925772195000496},
  volume = {8},
  year = {1997}
}

Downloads: 0

{"_id":"7wKXYSjyEGjrHDezP","authorIDs":[],"author_short":["Fukuda, K.","Liebling, T.<nbsp>M.","Margot, F."],"bibbaseid":"fukuda-liebling-margot-analysisofbacktrackalgorithmsforlistingallverticesandallfacesofaconvexpolyhedron-1997","bibdata":{"abstract":"In this paper, we investigate the applicability of backtrack technique to solve the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtrack algorithm for the face enumeration problem whose space complexity is polynomial in the input size, but the vertex enumeration problem requires a backtrack algorithm to solve a decision problem, called the restricted vertex problem, for each output, which is shown to be NP-complete. Some related NP-complete problems associated with a system of linear inequalities are also discussed, including the optimal vertex problems for polyhedra and arrangements of hyperplanes.","author":["Fukuda, Komei","Liebling, Thomas M.","Margot, Fraņcois"],"author_short":["Fukuda, K.","Liebling, T.<nbsp>M.","Margot, F."],"bibtex":"@article{ Fukuda1997,\n abstract = {In this paper, we investigate the applicability of backtrack technique to solve the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtrack algorithm for the face enumeration problem whose space complexity is polynomial in the input size, but the vertex enumeration problem requires a backtrack algorithm to solve a decision problem, called the restricted vertex problem, for each output, which is shown to be NP-complete. Some related NP-complete problems associated with a system of linear inequalities are also discussed, including the optimal vertex problems for polyhedra and arrangements of hyperplanes.},\n author = {Fukuda, Komei and Liebling, Thomas M. and Margot, Fraņ{c}ois},\n doi = {10.1016/0925-7721(95)00049-6},\n file = {:Users/KunihiroWASA/Dropbox/paper/1997/Fukuda, Liebling, Margot, Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, 1997.pdf:pdf},\n issn = {09257721},\n journal = {Computational Geometry},\n month = {June},\n number = {1},\n pages = {1--12},\n title = {{Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron}},\n url = {http://www.sciencedirect.com/science/article/pii/0925772195000496 http://linkinghub.elsevier.com/retrieve/pii/0925772195000496},\n volume = {8},\n year = {1997}\n}","bibtype":"article","doi":"10.1016/0925-7721(95)00049-6","file":":Users/KunihiroWASA/Dropbox/paper/1997/Fukuda, Liebling, Margot, Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, 1997.pdf:pdf","id":"Fukuda1997","issn":"09257721","journal":"Computational Geometry","key":"Fukuda1997","month":"June","number":"1","pages":"1--12","title":"Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron","type":"article","url":"http://www.sciencedirect.com/science/article/pii/0925772195000496 http://linkinghub.elsevier.com/retrieve/pii/0925772195000496","volume":"8","year":"1997","bibbaseid":"fukuda-liebling-margot-analysisofbacktrackalgorithmsforlistingallverticesandallfacesofaconvexpolyhedron-1997","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/0925772195000496 http://linkinghub.elsevier.com/retrieve/pii/0925772195000496"},"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:45.161Z","downloads":0,"keywords":[],"search_terms":["analysis","backtrack","algorithms","listing","vertices","faces","convex","polyhedron","fukuda","liebling","margot"],"title":"Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron","year":1997,"dataSources":["YRMeqhMHoNu9HzJoC"]}