tutorial

Separation by Convex Pseudo-Circles

Authors:

Nicolas Chevallier,

Augustin Fruchard,

Dominique Schmitt,

Jean-Claude SpehnerAuthors Info & Claims

SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

Pages 444 - 453

https://doi.org/10.1145/2582112.2582148

Published: 08 June 2014 Publication History

Abstract

Let S be a finite set of n points in the plane in general position. We prove that every inclusion-maximal family of subsets of S separable by convex pseudo-circles has the same cardinal (n 0)+(n 1)+(n 2)+(n 3). This number does not depend on the configuration of S and is the same as the number of subsets of S separable by true circles. Buzaglo, Holzman, and Pinchasi already showed that it is an upper bound for the number of subsets separable by (non necessarily convex) pseudo-circles.

In fact, we first count the number of elements in a maximal family of k-subsets of S separable by convex pseudo-circles, for a given k. From a well known result of Lee, when the set S has no four cocircular points, it admits 2kn − n − k2 + 1 − Σ k−1 i=1 a(i)(S) k-point subsets separable by true circles, where a(i) (S) is the number of i-sets of S. Here we show that this result still holds for convex pseudo-circles. In particular, this means that the number of k-subsets of S separable by a maximal family of convex pseudo-circles is an invariant of S: It does not depend on the choice of the maximal family.

To prove this result, we introduce a graph that generalizes the dual graph of the order-k Voronoi diagram, and whose vertices are the k-subsets of S separable by a maximal family of convex pseudo-circles. In order to count the number of vertices of this graph, we first show that it admits a planar realization which is a triangulation. It turns out (but is not detailed in the present paper) that these triangulations are the centroid triangulations defined by Liu and Snoeyink.

References

[1]

A. Andrzejak and K. Fukuda. Optimization over k-set polytopes and efficient k-set enumeration. In Proc. 6th Workshop Algorithms Data Struct., volume 1663 of Lecture Notes Comput. Sci., pages 1--12. Springer-Verlag, 1999.

Digital Library

[2]

A. Andrzejak and E. Welzl. In between k-sets, j-facets, and i-faces: (i, j)-partitions. Discrete Comput. Geom., 29:105--131, 2003.

[3]

F. Aurenhammer and O. Schwarzkopf. A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. Internat. J. Comput. Geom. Appl., 2:363--381, 1992.

[4]

S. Buzaglo, R. Holzman, and R. Pinchasi. On s-intersecting curves and related problems. In Proc. ACM Sympos. Comput. Geom., pages 79--84, 2008.

Digital Library

[5]

N. Chevallier, A. Fruchard, D. Schmitt, and J.-C. Spehner. Separation by convex pseudo-circles. Manuscript, 44 pages.

[6]

T. K. Dey. Improved bounds on planar k-sets and related problems. Discrete Comput. Geom., 19:373--382, 1998.

[7]

H. Edelsbrunner, P. Valtr, and E. Welzl. Cutting dense point sets in half. Discrete Comput. Geom., 17:243--255, 1997.

Digital Library

[8]

W. El Oraiby, D. Schmitt, and J.-C. Spehner. Centroid triangulations from k-sets. Internat. J. Comput. Geom. Appl., 21(06):635--659, 2011.

[9]

D. T. Lee. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput., C-31:478--487, 1982.

Digital Library

[10]

Y. Liu and J. Snoeyink. Quadratic and cubic B-splines by generalizing higher-order Voronoi diagrams. In Proc. ACM Sympos. Comput. Geom., pages 150--157, 2007.

Digital Library

[11]

R. Pinchasi and G. Rote. On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs. Israel J. Math., 172:337--348, 2009.

[12]

N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 25:80--83, 1972.

[13]

D. Schmitt and J.-C. Spehner. On Delaunay and Voronoi diagrams of order k in the plane. In Proc. 3rd Canad. Conf. Comput. Geom., pages 29--32, 1991.

[14]

S. Shelah. A combinatorial problem, stability and order for models and theories in infinite languages. Pacific J. Math., 41:247--261, 1972.

[15]

J. Steiner. Einige Gesetze über die Theilung der Ebene und des Raumes. J. reine und angew. Math., 1:349--364, 1826.

[16]

G. Tóth. Point sets with many k-sets. Discrete Comput. Geom., 26(2):187--194, 2001.

Digital Library

[17]

V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequences of events to their probabilities. Theory Probab. Appl., 16:264--280, 1971.

Cited By

Leroux BRademacher L(2022)Algebraic k-Sets and Generally Neighborly EmbeddingsDiscrete & Computational Geometry10.1007/s00454-021-00340-1Online publication date: 17-Jan-2022
https://doi.org/10.1007/s00454-021-00340-1
Chevallier NFruchard ASchmitt DSpehner J(2020)Separation by Convex Pseudo-CirclesDiscrete & Computational Geometry10.1007/s00454-020-00190-3Online publication date: 31-Mar-2020
https://doi.org/10.1007/s00454-020-00190-3
Schmitt D(2019)Bivariate B-Splines from Convex Pseudo-circle ConfigurationsFundamentals of Computation Theory10.1007/978-3-030-25027-0_23(335-349)Online publication date: 10-Jul-2019
https://doi.org/10.1007/978-3-030-25027-0_23

Index Terms

Separation by Convex Pseudo-Circles
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration

Recommendations

Separation by Convex Pseudo-Circles
Abstract
Let S be a finite set of n points in the plane in general position. We prove that every inclusion-maximal family of subsets of S separable by convex pseudo-circles has the same cardinal $(\begin{matrix} n \\ 0 \end{matrix}) + (\begin{matrix} n \\ 1 \end{matrix}) + (\begin{matrix} n \\ 2 \end{matrix}) + (\begin{matrix} n \\ 3 \end{matrix})$ . This number does not depend on the configuration ...
Lenses in arrangements of pseudo-circles and their applications

A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if the closed ...
Lenses in arrangements of pseudo-circles and their applications
SCG '02: Proceedings of the eighteenth annual symposium on Computational geometry

(MATH) A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

June 2014

588 pages

ISBN:9781450325943

DOI:10.1145/2582112

Program Chairs:
Siu-Wing Cheng
HKUST
,
Olivier Devillers
INRIA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

SOCG'14

SOCG'14: Annual Symposium on Computational Geometry

June 8 - 11, 2014

Kyoto, Japan

Acceptance Rates

SOCG'14 Paper Acceptance Rate 60 of 175 submissions, 34%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
92
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Leroux BRademacher L(2022)Algebraic k-Sets and Generally Neighborly EmbeddingsDiscrete & Computational Geometry10.1007/s00454-021-00340-1Online publication date: 17-Jan-2022
https://doi.org/10.1007/s00454-021-00340-1
Chevallier NFruchard ASchmitt DSpehner J(2020)Separation by Convex Pseudo-CirclesDiscrete & Computational Geometry10.1007/s00454-020-00190-3Online publication date: 31-Mar-2020
https://doi.org/10.1007/s00454-020-00190-3
Schmitt D(2019)Bivariate B-Splines from Convex Pseudo-circle ConfigurationsFundamentals of Computation Theory10.1007/978-3-030-25027-0_23(335-349)Online publication date: 10-Jul-2019
https://doi.org/10.1007/978-3-030-25027-0_23

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents