@article {38527,
	title = {Testing simple polygons},
	journal = {Computational GeometryComputational Geometry},
	volume = {8},
	year = {1997},
	type = {10.1016/S0925-7721(96)00015-6},
	abstract = {We consider the problem of verifying a simple polygon in the plane using {\textquotedblleft}test points{\textquotedblright}. A test point is a geometric probe that takes as input a point in Euclidean space, and returns {\textquotedblleft}+{\textquotedblright} if the point is inside the object being probed or {\textquotedblleft}-{\textquotedblright} if it is outside. A verification procedure takes as input a description of a target object, including its location and orientation, and it produces a set of test points that are used to verify whether a test object matches the description. We give a procedure for verifying an n-sided, non-degenerate, simple target polygon using 5n test points. This testing strategy works even if the test polygon has n + 1 vertices, and we show a lower bound of 3n + 1 test points for this case. We also give algorithms using O(n) test points for simple polygons that may be degenerate and for test polygons that may have up to n + 2 vertices. All of these algorithms work for polygons with holes. We also discuss extensions of our results to higher dimensions.},
	keywords = {probing, Testing, Verifying},
	isbn = {0925-7721},
	author = {Arkin, Esther M. and Belleville, Patrice and Mitchell, Joseph S. B. and Mount, Dave and Romanik, Kathleen and Salzberg, Steven and Souvaine, Diane}
}
@proceedings {38208,
	title = {A distributed algorithm for ear decomposition},
	year = {1993},
	month = {1993},
	publisher = {IEEE},
	type = {10.1109/ICCI.1993.315382},
	abstract = {A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition},
	keywords = {Asynchronous communication, asynchronous communication network, Automata, Communication networks, computational complexity, Computer networks, Computer science, decomposition graph, distributed algorithm, distributed algorithms, Distributed computing, Ear, ear decomposition, graph theory, message-optimal, network decomposition, sorting, Testing, time-optimal},
	isbn = {0-8186-4212-2},
	author = {Sridhar Hannenhalli and Perumalla, K. and Chandrasekharan, N. and Sridhar, R.}
}
