2 Search Results for "Clarkson, Michael"

Document
DOI: 10.4230/LIPIcs.ESA.2019.22
Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets

Authors: Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, and Marc Glisse

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are most of the time space and time optimal in the worst-case, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst-case. For example, it is known that the Delaunay triangulations of nicely distributed points on polyhedral surfaces in E^3 has linear complexity, as opposed to a worst-case quadratic complexity. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the case of nicely distributed points on polyhedral surfaces, the complexity of the usual RIC is O(n log n), which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. Our proofs also work for some other notions of nicely distributed point sets, such as (epsilon, kappa)-samples. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.
Cite as

Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, and Marc Glisse. Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.ESA.2019.22,
  author =	{Boissonnat, Jean-Daniel and Devillers, Olivier and Dutta, Kunal and Glisse, Marc},
  title =	{{Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.22},
  URN =		{urn:nbn:de:0030-drops-111437},
  doi =		{10.4230/LIPIcs.ESA.2019.22},
  annote =	{Keywords: Randomized incremental construction, Delaunay triangulations, Voronoi diagrams, polyhedral surfaces, probabilistic analysis}
}
Document
DOI: 10.4230/DagSemProc.07311.5
Civitas: A Secure Remote Voting System

Authors: Michael Clarkson, Stephen Chong, and Andrew Myers

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
Civitas is the first implementation of a coercion-resistant, universally verifiable, remote voting scheme. This paper describes the design of Civitas, details the cryptographic protocols used in its construction, and illustrates how language-enforced information-flow security policies yield assurance in the implementation. The performance of Civitas scales well in the number of voters and offers reasonable tradeoffs between time, cost, and security. These results suggest that secure electronic voting is achievable. The name of this system as presented at Dagstuhl was CIVS. In August 2007, the name was changed to Civitas. For more information, see the Civitas website at http://www.cs.cornell.edu/projects/civitas.
Cite as

Michael Clarkson, Stephen Chong, and Andrew Myers. Civitas: A Secure Remote Voting System. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{clarkson_et_al:DagSemProc.07311.5,
  author =	{Clarkson, Michael and Chong, Stephen and Myers, Andrew},
  title =	{{Civitas: A Secure Remote Voting System}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--47},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.5},
  URN =		{urn:nbn:de:0030-drops-12960},
  doi =		{10.4230/DagSemProc.07311.5},
  annote =	{Keywords: Electronic voting, coercion resistance, voter registration, secure bulletin boards, cryptographic protocols}
}
  • Refine by Author
  • 1 Boissonnat, Jean-Daniel
  • 1 Chong, Stephen
  • 1 Clarkson, Michael
  • 1 Devillers, Olivier
  • 1 Dutta, Kunal
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Delaunay triangulations
  • 1 Electronic voting
  • 1 Randomized incremental construction
  • 1 Voronoi diagrams
  • 1 coercion resistance
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact