NDLI: Double-permutation sequences and pseudoline transversals

Please wait, while we are loading the content...

Forbidden patterns and unit distances

Mountain reduction, block matching, and applications in intensity-modulated radiation therapy

Certifying and constructing minimally rigid graphs in the plane

An exact, complete and efficient implementation for computing planar maps of quadric intersection curves

Smaller coresets for k-median and k-means clustering

Cache-oblivious planar orthogonal range searching and counting

Learning smooth objects by probing

A time-optimal delaunay refinement algorithm in two dimensions

Inclusion-exclusion formulas from independent complexes

Vertical ray shooting for fat objects

Minimum dilation stars

Learning smooth objects by probing

Clustered planarity

Hadwiger and Helly-type theorems for disjoint unit spheres in $R^{3}$

Dynamic maintenance of molecular surfaces under conformational changes

Pointed and colored binary encompassing trees

On the exact computation of the topology of real algebraic curves

Improved approximation algorithms for geometric set cover

Cache-oblivious R-trees

Provable dimension detection using principal component analysis

Star splaying: an algorithm for repairing delaunay triangulations and convex hulls

Weak feature size and persistent homology: computing homology of solids in $R^{n}$ from noisy data samples

The skip quadtree: a simple dynamic data structure for multidimensional data

Finding the best shortcut in a geometric network

Reconstructing collections of arbitrary curves

Double-permutation sequences and pseudoline transversals

Incidences of not-too-degenerate hyperplanes

The lifting model for reconfiguration

Abstract order type extension and new results on the rectilinear crossing number

Shortest path amidst disc obstacles is computable

Sampling in dynamic data streams and applications

Multi-pass geometric algorithms

Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction

Stability of persistence diagrams

Space efficient dynamic orthogonal range reporting

Energy-aware stage illumination

Efficient geometric techniques for reconstructing 3D vessel trees from biplane image

Almost tight bound for a single cell in an arrangement of convex polyhedra in $R^{3}$

The visibility--voronoi complex and its applications

Fast construction of nets in low dimensional metrics, and their applications

Kinetic sorting and kinetic convex hulls

Inequalities for the curvature of curves and surfaces

Efficient computation of query point visibility in polygons with holes

Guarding a terrain by two watchtowers

Implementing time-varying contour trees

Curvature-bounded traversals of narrow corridors

Maximizing the overlap of two planar convex sets under rigid motions

Rectangular cartograms: construction & animation

Animation of curve constrained drawings of planar graphs

Covering points with a polygon

1-link shortest paths in weighted regions

An extension of CGAL to the oriented projective plane $T^{2}$ and its dynamic visualization system

Exact minkowski sums of convex polyhedra

Fast and reliable collision detection using graphics processors

Double-permutation sequences and pseudoline transversals

Content Provider	ACM Digital Library
Author	Goodman, Jacob E.
Abstract	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.
Starting Page	159
Ending Page	159
Page Count	1
File Format	PDF
ISBN	1581139918
DOI	10.1145/1064092.1064094
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Convex set Double-permutation sequence Pseudoline Transversal
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in