David Avis, Komei Fukuda  Home/Search
Context Related
| mutt.cs.mcgill.ca/pub/doc...AF96a.ps.gz cgm.cs.mcgill.ca/~avis/do...AF96a.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: mutt.cs.mcgill.ca/pub/do...online (more) Homepages: D.Avis K.Fukuda HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: The reverse search technique has been recently introduced by the authors for efficient enumeration of vertices of polyhedra and arrangements. In this paper, we develop this idea in a general framework and show its broader applications to various problems in operations research, combinatorics, and geometry. In particular, we propose new algorithms for listing (i) all triangulations of a set of n points in the plane, (ii) all cells in a hyperplane arrangement in R d , (iii) all spanning... (Update)
Context of citations to this paper: More
...are reverse search and walk to root approaches. The reverse search method is known to be an exceedingly space ecient technique [AF96,Nie00]. Data structures of the proposed algorithm can be naturally used by the reverse search and it is possible to reduce the memory...
...position in the plane, find all the triangulations whose vertex set is S and edge set includes the convex hull of S. Avis and Fukuda [2] devised a reverse search method which allows to enumerate triangulations in Theta(nt(S) time, where t(S) is the number of...
Cited by: More
Counting Lattice Triangulations - Kaibel, Ziegler (Correct)
How to Employ Reverse Search in Distributed Single.. - Brim, Cerna, Krcal.. (2001) (Correct)
An Efficient Algorithm for Enumeration of Triangulations - Bespamyatnikh (2001) (Correct)
Active bibliography (related documents): More All
1.1: An Optimal Algorithm for Scanning All Spanning Trees of.. - Shioura, Tamura, Uno (1994) (Correct)
0.8: Efficiently Scanning All Spanning Trees of an Undirected Graph - Shioura, Tamura (1993) (Correct)
0.5: Reconstructing visible regions from visible segments - Franklin, al. (1986) (Correct)
Similar documents based on text: More All
0.2: Double Description Method Revisited - Fukuda, Prodon (1996) (Correct)
0.2: Frequently Asked Questions in Polyhedral Computation - Fukuda (2000) (Correct)
0.1: Convexity Recognition of the Union of Polyhedra - Bemporad, Fukuda, Torrisi (2000) (Correct)
Related documents from co-citation: More All
8: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and.. (context) - Avis, Fukuda - 1992
4: Encoding A Triangulation As A Permutation Of Its Point Set - Denny, Sohler - 1997
4: The path of a triangulation - Aichholzer - 1999
BibTeX entry: (Update)
D. Avis and K. Fukuda, "Reverse Search for Enumeration", Discrete Applied Mathematics, to appear. http://citeseer.nj.nec.com/avis93reverse.html More
@misc{ avis-reverse,
author = "D. Avis and K. Fukuda",
title = "Reverse Search for Enumeration",
text = "D. Avis and K. Fukuda, Reverse Search for Enumeration, Discrete Applied
Mathematics, to appear.",
url = "citeseer.nj.nec.com/avis93reverse.html" }
Citations (may not include all citations):593 Theory of Linear and Integer programming (context) - Schrijver - 1986
417 Algorithms in Combinatorial Geometry (context) - Edelsbrunner - 1987
390 Data Structures and Algorithms (context) - Aho, an et al. - 1987
219 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
133 Matroid Theory (context) - Welsh - 1976
92 Combinatorial Optimization (context) - Papadimitriou, Steiglitz - 1982
59 A pivoting algorithm for convex hulls and vertex enumeration.. (context) - Avis, Fukuda - 1992
26 Annals of Discrete Mathematics (context) - Fujishige, Functions - 1991
16 Generating Linear Extensions Fast - Pruesse, Ruskey
9 A structured program to generate all topological sorting arr.. (context) - Knuth, Szwarcfiter - 1974
5 A C implementation of the reverse search vertex enumeration .. (context) - Avis - 1992
5 A basis enumeration algorithm for linear systems with geomet.. (context) - Avis, Fukuda - 1991
4 Bounds on backtrack algorithms for listing cycles, paths, an.. (context) - Read, Tarjan - 1975
3 A note on Delaunay diagonal flips (context) - Fortune - 1987
3 Algorithms for finding all the spanning trees in undirected .. - Matsui - 1993
3 Partion of space (context) - Buck - 1943
3 Efficiently scanning all spanning trees of an undirected gra.. - Shioura, Tamura - 1993
2 Notes on Bland's pivoting rule (context) - Avis, Chv'atal - 1978
2 the priority approach to hidden surface algorithms (context) - Yao - 1980
1 Combinatorical face enumeration in arrangements and oriented.. (context) - Fukuda, Saito et al. - 1991
1 Bounding the number of k-faces in arrangements of hyperplane.. (context) - Fukuda, Saito et al. - 1991
1 Mathematica package: Vertex enumeration for convex polyhedra.. (context) - Fukuda, Mizukoshi - 1991
1 Static and dynamic weighted Delaunay triangulations in the E.. (context) - Telley - 1990
The graph only includes citing articles where the year of publication is known.
Documents on the same site (ftp://mutt.cs.mcgill.ca/pub/doc/online.html): More
Computational Aspects of Helly's Theorem and its Relatives - David Avis And (1991) (Correct)
How Good are Convex Hull Algorithms? - Avis, Bremner, Seidel (1997) (Correct)
On the Existence of a Point Subset with a Specified Number.. - David Avis School (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute