In joint work with Ricky Pollack about 25 years ago we defined an encoding of a configuration of points in the plane by what we called its circular sequence of permutations. This notion was subsequently used, both by us and others, to study an array of problems in combinatorial geometry.Recently we noticed that a similar technique can be used to encode combinatorial properties of a collection of mutually disjoint compact convex sets in the plane, and that we can use it, for example, to give a new proof of the Edelsbrunner-Sharir "(2n-2)-theorem" on the maximum number of geometric permutations of a collection of such sets. At the same time this new proof generalizes the Edelsbrunner-Sharir result to the case of a family of compact connected sets in the plane, separated by pseudolines, every two having four double-tangent pseudolines, with all the pseudolines together forming an arrangement. In this talk we will describe the encoding, define the notion of geometric permutation for such a collection, and discuss the proof.The same encoding, which associates to a family of n sets a sequence of permutations of 1, 1, 2, 2,..., n, n, shows promise of being applicable to a number of other problems concerning combinatorial properties of collections of convex sets.The talk is based on ongoing joint work with Ricky Pollack.

Article A Helly-type theorem for hyperplane transversals to well-separated convex sets Share on Authors: Boris Aronov Polytechnic University, Brooklyn, NY Polytechnic University, Brooklyn, NYView Profile , Jacob E. Goodman City College, City University of New York, New York, NY City College, City University of New York, New York, NYView Profile , Richard Pollack Courant Institute of Mathematical Sciences, New York University, New York, NY Courant Institute of Mathematical Sciences, New York University, New York, NYView Profile , Rephael Wenger The Ohio State University, Columbus, OH The Ohio State University, Columbus, OHView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 57–63https://doi.org/10.1145/336154.336178Online:01 May 2000Publication History 0citation233DownloadsMetricsTotal Citations0Total Downloads233Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We prove that a (k-1)-separated family of n compact convex sets in Rd can be met byk-transversals in at most O(d)d2((2k+1-2 / k) (n / k+1))k(d-k) or, for fixed k and d, O(nk(k+1)(d-k)) different order types. This is the first non-trivial bound for 1

Article Free Access Share on There is a universal topological plane Authors: Jacob E. Goodman View Profile , Richard Pollack View Profile , Rephael Wenger View Profile , Tudor Zamfirescu View Profile Authors Info & Claims SCG '92: Proceedings of the eighth annual symposium on Computational geometryJuly 1992Pages 171–176https://doi.org/10.1145/142675.142714Published:01 July 1992Publication History 0citation272DownloadsMetricsTotal Citations0Total Downloads272Last 12 Months25Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteeReaderPDF

We show that the maximum combinatorial complexity of the space of hyperplane transversals to a family of n separated and strictly convex sets in Rd is Θ(n⌊d/2⌋), which generalizes results of Edelsbrunner and Sharir in the plane. As a key step in the argument, we show that the space of hyperplanes tangent to κ ≤ d separated and strictly convex sets in Rd is a topological (d - κ)-sphere.

We give doubly exponential upper and lower bounds on the size of the smallest grid on which we can embed every planar configuration of n points in general position up to order type. The lower bound is achieved by the construction of a widely dispersed “rigid” configuration which is then modified to one in general position by recent techniques of Sturmfels and White, while the upper bound uses recent results of Grigor'ev and Vorobjou on the solution of simultaneous inequalities. This provides a sharp answer to a question first posed by Chazelle.

Article Free Access Share on Modeling planar configurations Authors: Jacob E. Goodman City College, CUNY City College, CUNYView Profile , Richard Pollack Courant Institute, NW Courant Institute, NWView Profile Authors Info & Claims SCG '85: Proceedings of the first annual symposium on Computational geometryJune 1985Pages 121–124https://doi.org/10.1145/323233.323250Published:01 June 1985Publication History 0citation169DownloadsMetricsTotal Citations0Total Downloads169Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We introduce a process called geometric sorting, which can be applied to an arbitrary configuration of points in d space, and which encodes in compact form the order properties of the configuration, just as the arrangement of a set of numbers in size place encodes its order properties. We give an algorithm for carrying out this sorting procedure in time $O(n^d \log n)$, which generalizes the optimum sorting time of $O(n\log n)$ for the linear case; In addition, we give an efficient algorithm for determining whether two randomly numbered configurations in $\mathbb{R}^d $ have the same order type, using a distinguished family of orderings of each. Finally, we indicate how this new concept of sorting can be applied to problems in pattern recognition, stereochemistry, and cluster analysis.