Abstract
Each test or feature in a classification system defines a set partition on a class of objects. Adding new features refines the classification, whereas deleting features may result in merging previously distinguished classes. As an illustration, consider the set of automobile types {VW Beetle, Toyota, Lexus, Cadillac}. The feature size partitions the cars into sets of small and large cars, {VW Beetle, Toyota}, {Lexus, Cadillac}. The feature domestic-origin partitions the cars into {VW Beetle, Toyota, Lexus, Cadillac}. The feature uglyshape distinguishes {VW Beetle, Cadillac} from {Toyota, Lexus}. Incorporating both size and origin induces the refined partition {VW Beetle, Toyota}, {Lexus}, {Cadillac}, whereas the union of all three features completely distinguishes the types of cars. In fact, size and uglyshape are sufficient for complete identification, so domestic-origin could be deleted from the set of features without affecting the induced partition.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
E. Arkin, H. Meijer, J. Mitchell, D. Rappaport, and S. Skiena. Decision trees for geometric objects. Int. J. Computational Geometry and Applications, 8:343–363, 1998.
Gruia Calinescu. A data structure for maintaining a partition. manuscript, 2000.
Bernard Chazelle, H. Edelsbrunner, M. Grigni, Leonidas J.Guibas, J. Hershberger, Micha Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulationsAlgorithmica, 12:54–68, 1994.
R. Cole and R. Hariharan. Dynamic LCA queries on trees. In Proc. Tenth ACM-SIAM Symp. Discrete Algorithms (SODA), pages 235–244, 1999.
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.
P. Dietz, K. Mehlhorn, R. Raman, and C. Uhrig. Lower bounds for set intersection queries. In Proc. Fourth ACM-SIAM Symp. Discrete Algorithms (SODA), pages 194–201, 1993.
J. Feigenbaum and S. Kannan. Dynamic graph algorithms. Handbook of Discrete and Combinatorial Mathematics, 1995.
R. Freimer, J. Mitchell, and C. Piatko. On the complexity of shattering using arrangements. In CCCG: Canadian Conference in Computational Geometry, 1990.
L. Guibas and R. Sedgewick. A bichromatic framework for balanced trees. In Proc. 19th IEEE Symp. Foundations of Computer Science, pages 8–21, 1978.
D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.
M. Habib, C. Paul, and L. Viennot. A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata. In Proc. Fifteenth STACS, pages 25–38. Springer-Verlag LNCS, 1998.
J. Hopcroft. An nlogn algorithm for minimizing the states in a finite automaton. In Z. Kohavi, editor, The theory of machines and computations, pages 189–196. Academic Press, New York, 1971.
J. Matoušek. More on cutting arrangements and spanning trees with low crossing number. Technical Report B-90-2, Fachbereich Mathematik, Freie Universität Berlin, Berlin, 1990.
R. Paige and R. Tarjan. Three partition refinement algorithms. SIAM J. Computing, 16:973–989, 1987.
G. Sazaklis, E. Arkin, J. Mitchell, and S. Skiena. Probe trees for touching character recognition. In Proc. International Conference on Imaging Science, Systems and Technology, (CISST), pages 282–289, Las Vegas, NV, 1998.
G. Sazaklis, E. Arkin, J. S. B. Mitchell, and S. Skiena. Geometric decision trees for optical character recognition. In Proc. of 13th Annual ACM Symposium on Computational Geometry, pages 490–492, Nice, France, June 1997.
R. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22:215–225, 1975.
E. Ukkonen. Constructing suffix trees on-line in linear time. In Intern. Federation of Information Processing (IFIP)’ 92, pages 484–492, 1992.
D. Yellin. Representing sets with constant time equality testing. In Proc. First ACM-SIAM Symp. Discrete Algorithms (SODA), pages 64–73, 1990.
D. Yellin. Algorithms for subset testing and finding maximal sets. In Proc. Third ACM-SIAM Symp. Discrete Algorithms (SODA), pages 386–392, 1992.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bender, M.A., Sethia, S., Skiena, S. (2000). Data Structures for Maintaining Set Partitions. In: Algorithm Theory - SWAT 2000. SWAT 2000. Lecture Notes in Computer Science, vol 1851. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44985-X_9
Download citation
DOI: https://doi.org/10.1007/3-540-44985-X_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67690-4
Online ISBN: 978-3-540-44985-0
eBook Packages: Springer Book Archive