TY - JOUR T1 - Testing simple polygons JF - Computational GeometryComputational Geometry Y1 - 1997 A1 - Arkin, Esther M. A1 - Belleville, Patrice A1 - Mitchell, Joseph S. B. A1 - Mount, Dave A1 - Romanik, Kathleen A1 - Salzberg, Steven A1 - Souvaine, Diane KW - probing KW - Testing KW - Verifying AB - We consider the problem of verifying a simple polygon in the plane using “test points”. A test point is a geometric probe that takes as input a point in Euclidean space, and returns “+” if the point is inside the object being probed or “−” 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. VL - 8 SN - 0925-7721 ER - TY - Generic T1 - A distributed algorithm for ear decomposition T2 - Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93 Y1 - 1993 A1 - Sridhar Hannenhalli A1 - Perumalla, K. A1 - Chandrasekharan, N. A1 - Sridhar, R. KW - Asynchronous communication KW - asynchronous communication network KW - Automata KW - Communication networks KW - computational complexity KW - Computer networks KW - Computer science KW - decomposition graph KW - distributed algorithm KW - distributed algorithms KW - Distributed computing KW - Ear KW - ear decomposition KW - graph theory KW - message-optimal KW - network decomposition KW - sorting KW - Testing KW - time-optimal AB - 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 JA - Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93 PB - IEEE SN - 0-8186-4212-2 ER -